bfs()
2024-08-20 10:39:19
发布于:广东
9阅读
0回复
0点赞
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
int n, m;
int ans = 0;
char a[maxn][maxn];
bool vis[maxn][maxn];
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
struct node{
int x, y;
}l, r;
void bfs(int x, int y){
queue<node> q;
q.push({x, y});
while(q.size()){
l = q.front();
q.pop();
for(int i = 0; i < 4; i++){
int nx = l.x + dir[i][0];
int ny = l.y + dir[i][1];
if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && !vis[nx][ny] && a[nx][ny] >= '1' && a[nx][ny] <= '9'){
vis[nx][ny] = true;
q.push({nx, ny});
}
}
}
}
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(a[i][j] >= '1' && a[i][j] <= '9' && !vis[i][j]){
bfs(i, j);
ans++;
}
}
}
cout << ans;
return 0;
}
这里空空如也
有帮助,赞一个