题目描述
由数字 0 组成的方阵中,有一任意形状闭合圈,闭合圈由数字 1 构成,围圈时只走上下左右 4 个方向。现要求把闭合圈内的所有空间都填写成 2 .例如: 6×6 的方阵( n=6 ),涂色前和涂色后的方阵如下:
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1
输入输出格式
输入格式:
每组测试数据第一行一个整数 n(1 \le n \le 30)n(1≤n≤30)
接下来 nn 行,由 00 和 11 组成的 n \times nn×n 的方阵。
方阵内只有一个闭合圈,圈内至少有一个 00 。
//感谢黄小U饮品指出本题数据和数据格式不一样. 已修改(输入格式)
输出格式:
已经填好数字 22 的完整方阵。
输入输出样例
输入样例#1:
6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1
输出样例#1:
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1
说明
1≤n1≤n≤30≤30
题解
由边缘开始搜索,凡是可以到达的的00全部改为−1−1,最后输出时特判一下。
#include <bits/stdc++.h>
using namespace std;
const int MAXN=50;
int mapp[MAXN][MAXN];
struct node{
int x,y;
};
int n;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
void bfs(int x,int y)
{
node p;
p.x=x;
p.y=y;
queue<node> q;
q.push(p);
while(!q.empty()) {
node s;
s=q.front();
q.pop();
for(int i=0;i<4;i++) {
int kx=s.x+dx[i];
int ky=s.y+dy[i];
if(kx>=0&&kx<n&&ky>=0&&ky<n&&mapp[kx][ky]==0)
{
node z;
z.x=kx;z.y=ky;
q.push(z);
mapp[kx][ky]=-1;
}
}
}
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&mapp[i][j]);
for(int i=0;i<n;i++){
if(mapp[0][i]==0) bfs(0,i);
if(mapp[n-1][i]==0) bfs(n-1,i);
if(mapp[i][0]==0) bfs(i,0);
if(mapp[i][n-1]==0) bfs(i,n-1);
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++) {
if(mapp[i][j]==-1) printf("0 ");
else if(mapp[i][j]==1) printf("1 ");
else if(mapp[i][j]==0) printf("2 ");
}
printf("\n");
}
return 0;
}