题目
题目原文请移步下面的链接
- https://www.luogu.com.cn/problem/P1162
- 参考题解：https://www.luogu.com.cn/problem/solution/P1162
- 标签：
搜索、广度优先搜索、BFS
题解
- 小码匠思路
- 这也是个比较标准的连通块了，既然中间的0不好找，我们就反向寻找外层的进行标记，再反向把未标记的0输出时改为2
- 外层的0很好找在于一个外层0构成的连通块一定有紧挨着边缘的，所以把四周走一遍就能覆盖掉外层0啦
- 官方题解
- 题解大家可移步看这里，很多童鞋写了各种解法
- https://www.luogu.com.cn/problem/solution/P1162代码
#include <bits/stdc .h>
using namespace std;
int a[103][103];
int n;
int len[10005];
int b[103][103];
struct edge {
int x, y;
};
queue<edge> v;
void bfs(int x, int y ) {
v.push({x, y});
while (!v.empty()) {
edge k = v.front();
v.pop();
if (k.x - 1 >= 0 && !b[k.x - 1][k.y] && a[k.x - 1][k.y] == 0) {
v.push({k.x - 1, k.y});
b[k.x - 1][k.y] = true;
}
if (k.x 1 < n && !b[k.x 1][k.y] && a[k.x 1][k.y] == 0) {
v.push({k.x 1, k.y});
b[k.x 1][k.y] = true;
}
if (k.y - 1 >= 0 && !b[k.x][k.y - 1] && a[k.x][k.y - 1] == 0) {
v.push({k.x, k.y - 1});
b[k.x][k.y - 1] = true;
}
if (k.y 1 < n && !b[k.x][k.y 1] && a[k.x][k.y 1] == 0) {
v.push({k.x, k.y 1});
b[k.x][k.y 1] = true;
}
}
}
int main () {
cin >> n;
for (int i = 0; i < n; i) {
for (int j = 0; j < n; j) {
cin >> a[i][j];
}
}
int ans = 0;
for (int i = 0; i < n; i) {
if (a[0][i] == 0 && !b[0][i]) {
bfs(0, i);
}
if (a[i][0] == 0 && !b[i][0]) {
bfs(i, 0);
}
if (a[n - 1][i] == 0 && !b[n - 1][i]) {
bfs(n - 1, i);
}
if (a[i][n - 1] == 0 && !b[i][n - 1]) {
bfs(i, n - 1);
}
}
for (int i = 0; i < n; i) {
for (int j = 0; j < n; j) {
if (a[i][j] == 0 && !b[i][j]) {
cout << 2 << " ";
continue;
}
cout << a[i][j] << " ";
}
cout << endl;
}
return 0;
}
