小码王——广度优先搜索搜(三)课后第一题
2025-02-15 11:04:20
发布于：广东
10阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
int n,m,maxn=0;
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
char mp[1505][1505];
bool vis[1505][1505];
struct node{int x;int y;};
bool check(int x,int y){
return x <= n&&x>=1&&y<=m&&y>=1&&!vis[x][y]&&mp[x][y]!='0';
}
void bfs(int x,int y){
queue<node>q;
q.push({x,y});
vis[x][y]=1;
while(!q.empty()){
node t = q.front();
q.pop();
for(int i = 0; i < 4; i++){
int nx = t.x+dx[i];
int ny = t.y+dy[i];
if(check(nx,ny)){
vis[nx][ny]=1;
q.push({nx,ny});
}
}
}
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> mp[i][j];
}
}
int cnt=0;
for(int i= 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(mp[i][j]!='0'&&!vis[i][j]){
bfs(i,j);
cnt++;
}
}
}
cout << cnt;
return 0;
}
这里空空如也
有帮助，赞一个