填涂颜色
题目描述
由数字 $0$ 组成的方阵中,有一任意形状闭合圈,闭合圈由数字 $1$ 构成,围圈时只走上下左右 $4$ 个方向。现要求把闭合圈内的所有空间都填写成 $2$。例如:$6\times 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$ 行,由 $0$ 和 $1$ 组成的 $n \times n$ 的方阵。
方阵内只有一个闭合圈,圈内至少有一个 $0$。
//感谢黄小U饮品指出本题数据和数据格式不一样. 已修改(输入格式)
输出格式
已经填好数字 $2$ 的完整方阵。
样例 #1
样例输入 #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
提示
对于 $100\%$ 的数据,$1 \le n \le 30$。
#include<iostream>
#include<cstring>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 35;
int n;
int g[N][N]; //地图
bool st[N][N];
PII q[N * N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void bfs(int x1, int y1){
q[0] = {x1, y1};
st[x1][y1] = true;
int hh =0, tt = 0;
while(hh <= tt){
auto t = q[hh++]; //取出队头
for(int i = 0; i < 4; i++){
int a = t.x + dx[i], b = t.y + dy[i];
if(a < 0 || a > n + 1 || b < 0 || b > n + 1) continue;
if(g[a][b] == 1) continue;
if(st[a][b]) continue;
st[a][b] = true;
q[++tt] = {a, b};
}
}
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
scanf("%d", &g[i][j]);
}
}
bfs(0, 0);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(g[i][j] == 0 && !st[i][j]){
g[i][j] = 2;
}
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
printf("%d ", g[i][j]);
}
printf("\n");
}
return 0;
}