填涂颜色
题目描述
由数字 \(0\) 组成的方阵中，有一任意形状的由数字 \(1\) 构成的闭合圈。现要求把闭合圈内的所有空间都填写成 \(2\)。例如：\(6\times 6\) 的方阵（\(n=6\)），涂色前和涂色后的方阵如下：
如果从某个 \(0\) 出发，只向上下左右 \(4\) 个方向移动且仅经过其他 \(0\) 的情况下，无法到达方阵的边界，就认为这个 \(0\) 在闭合圈内。闭合圈不一定是环形的，可以是任意形状，但保证闭合圈内的 \(0\) 是连通的（两两之间可以相互到达）。
0 0 0 0 0 0
0 0 0 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 1 0 1
1 1 1 1 1 1
0 0 0 0 0 0
0 0 0 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 1 2 1
1 1 1 1 1 1
输入格式
每组测试数据第一行一个整数 \(n(1 \le n \le 30)\)。
接下来 \(n\) 行，由 \(0\) 和 \(1\) 组成的 \(n \times n\) 的方阵。
方阵内只有一个闭合圈，圈内至少有一个 \(0\)。
输出格式
已经填好数字 \(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\)。
首先，我们可以看到题目的算法标签是bfs，所以先可以把模版写完
剩下的就不用多说了，直接瀑布填充就行了
话不多说，show me code！
#include<bits/stdc++.h>
using namespace std;
int a[31][31];
int b[31][31];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int n;
struct node
{
int x, y;
};
void bfs()
{
int cnt = 1;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(!a[i][j] && !b[i][j])
{
bool flag = true;
queue<node> q;
q.push({i, j});
b[i][j] = cnt;
while(!q.empty())
{
node t = q.front();
q.pop();
for(int k = 0; k < 4; k++)
{
int nx = t.x + dx[k], ny = t.y + dy[k];
//cout << nx << " " << ny << endl;
if(nx < 1 || nx > n || ny < 1 || ny > n)
{
flag = false;
}
else if(!(a[nx][ny] || b[nx][ny]))
{
q.push({nx, ny});
b[nx][ny] = cnt;
}
}
}
//cout << flag << endl;
if(flag)
{
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(b[i][j] == cnt)
{
a[i][j] = 2;
}
}
}
}
cnt++;
}
}
}
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
cin >> a[i][j];
}
}
bfs();
/* for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
cout << b[i][j] << " ";
}
cout << endl;
}*/
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
cout << a[i][j] << " ";
}
cout << endl;
}
return 0;
}