题目
题目原文请移步下面的链接
- https://www.luogu.com.cn/problem/P1451
- 参考题解：https://www.luogu.com.cn/problem/solution/P1451
- 标签：
搜索、广度优先搜索、BFS
题解
- 小码匠思路
- 如果有有心人就会发现，他一行读入的数字间是没有空格的，这个时候你就只能用char来读入了，string还要拆分（我卡这里了至少20分钟，死亡微笑ing）
- 是个连通块的题，不嫌麻烦打if的是我本人没得跑了，直接先双层循环找没有访问过的细胞然后bfs确定连通块就行了
- 对本蒟蒻来说，这里最大的坑点不在于中间的逻辑，而是读入
- 官方题解
- 题解大家可移步看这里，很多童鞋写了各种解法
- https://www.luogu.com.cn/problem/solution/P1451
代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
int a[103][103];
int n, m;
int len[10005];
int b[103][103];
struct edge {
int x, y;
};
int main () {
cin >> n >> m;
for (int i = 0; i < n; i) {
for (int j = 0; j < m; j) {
char c;
cin >> c;
a[i][j] = c- '0';
if(a[i][j] == 0) {
b[i][j] = true;
}
}
}
int ans = 0;
for (int i = 0; i < n; i) {
for (int j = 0; j < m; j) {
queue<edge> v;
if (!b[i][j]){
v.push({i, j});
ans;
while (!v.empty()) {
edge k = v.front();
v.pop();
if (k.x - 1 >= 0 && !b[k.x - 1][k.y]) {
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]) {
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]) {
v.push({k.x, k.y - 1});
b[k.x][k.y - 1] = true;
}
if (k.y 1 < m && !b[k.x][k.y 1]) {
v.push({k.x, k.y 1});
b[k.x][k.y 1] = true;
}
}
}
}
}
cout << ans;
return 0;
}
