AC代码
bfs
```cpp
#include<bits/stdc++.h>
using namespace std;
#define N 1000
#define M 1000
int n,m;
char a[N][M];
int vis[N][M];
struct point {
int x,y;
};
queue <point> q;
int dx[4]= {-1,1,0,0};
int dy[4]= {0,0,-1,1};
int color;
void bfs(int x,int y) {
point tmp;
tmp.x=x;
tmp.y=y;
q.push(tmp);
while(!q.empty()) {
tmp=q.front();
q.pop();
for(int i=0;i<4;i++) {
point np=tmp;
np.x+=dx[i];
np.y+=dy[i];
if(np.x>=0&&np.x<n&&np.y>=0&&np.y<m&&!vis[np.x][np.y]&&a[np.x][np.y]!='0'){
q.push(np);
}
}
vis[tmp.x][tmp.y]=color;
}
}
int main() {
scanf("%d%d",&n,&m);
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
cin>>a[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(!vis[i][j]&&a[i][j]!='0'){//发现没被染色的细胞
color++;
bfs(i,j);
}
}
}
printf("%d\n",color);
return 0;
}
```
dfs
```
#include<bits/stdc++.h>
using namespace std;
#define N 1000
#define M 1000
int n,m;
int num;
char a[N][M];
int dx[4]= {-1,1,0,0};
int dy[4]= {0,0,-1,1};
void dfs(int x,int y) {
int i,j,newx,newy;
a[x][y]='0';
for(i=0; i<4; i++) {
newx=x+dx[i];
newy=y+dy[i];
if(newx<n && newx>=0 && newy<m && newy>=0) {
if(a[newx][newy]!='0')
dfs(newx,newy);
}
}
}
int main() {
int i,j;
scanf("%d%d",&n,&m);
getchar();
for(i=0; i<n; i++)
scanf("%s",&a[i]);
for(i=0; i<n; i++) {
for(j=0; j<m; j++) {
if(a[i][j]!='0') {
num++;
dfs(i,j);
}
}
}
printf("%d\n",num);
return 0;
}
```
by yueyifan @ 2024-02-07 16:04:19
@
chenxi797
by yueyifan @ 2024-02-07 16:06:09