这题要用dfs去会更简单。
这题是一道联通块
献上代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int a[105][105];
int m,n,cnt=0;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void dfs(int x,int y)
{
a[x][y]=0;
for(int i=0;i<4;i++)
{
int nx=x+dx[i],ny=y+dy[i];
if(nx>0&&nx<=n&&ny>0&&ny<=m&&a[nx][ny]!=0)dfs(nx,ny);
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%1d",&a[i][j]);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]==0)
{
continue;
}
dfs(i,j);
cnt++;
}
}
cout<<cnt;
return 0;
}
```
by zyhe2013 @ 2024-03-29 14:46:06
@[jinxc](/user/865834) 求关
by zyhe2013 @ 2024-03-29 14:46:48
@[jinxc](/user/865834)
```cpp
#include <bits/stdc++.h>
using namespace std;
char a[101][101];
int vis[101][101];
int dd[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int n, m, ans = 0, head = 0, tail = 0;
struct node {
int x, y;
} q[114514];
void bfs(int x, int y) {
ans++;
head = 1;
tail = 1;
q[tail].x = x;
q[tail++].y = y;
while (head <= tail) {
vis[q[head].x][q[head].y] = ans;
for (int i = 0; i < 4; i++) {
int xx = dd[i][0] + q[head].x;
int yy = dd[i][1] + q[head].y;
if (xx>=1 && xx<=n && yy>=1 && yy<=m && a[xx][yy] != '0' && vis[xx][yy] == 0) {
q[++tail].x = xx;
q[tail].y = yy;
}
}
head++;
}
}
int main() {
cin >> n >> m;
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (vis[i][j] == 0 && a[i][j] != '0') {
bfs(i, j);
// cout << 1 << endl;
}
}
}
// for(int i=1;i<=n;i++)
// {
// for(int j=1;j<=m;j++)
// {
// cout<<vis[i][j];
// }
// cout<<'\n';
// }
cout << ans;
return 0;
}
```
by hanruchen_rainbowcat @ 2024-03-29 15:00:27
@[jinxc](/user/865834) 手写队列炸了，vis的操作也炸了
by hanruchen_rainbowcat @ 2024-03-29 15:01:02
@[zyhe2013](/user/905073) 感谢，已关%%%
by Wuski @ 2024-03-29 22:38:53
@[hanruchen_rainbowcat](/user/533160) 感谢指出错误，已关%%%
by Wuski @ 2024-03-29 22:39:21
@[zyhe2013](/user/905073) 我们老师让我用bfs
by Wuski @ 2024-03-29 22:40:00