P1451 求细胞数量(广搜)

题意:就是0把是所有细胞圈起来了。而被圈起来的是所有数字全部为一个细胞问有多少个这样的细胞。(mmp,我读半天题)

思路:广搜索。就是,0的话就不放入了,不为0的话,就进入队列,然后,再看它的4个方向的格子是不是非0,非0就进入队列,这样就可以把一个细胞都搜索到。当进行下一次搜索就ans++;

#include<iostream>
#include<queue>
using namespace std; const int maxn = ; struct node{
int x, y;
}a, b;
bool f[maxn][maxn];
char s[maxn];
int dx[] = { , , , , - };
int dy[] = { , -, , , };
int n, m, ans;
int tail, head;
queue<node>ss; int main(){
cin >> n >> m;
for (int i = ; i <= n; ++i){
cin >> s;
for (int j = ; s[j];++j)
if (s[j] != ''){
f[i][j + ] = ;
}
}
for (int i = ; i <= n;++i)
for (int j = ; j <= m;++j)
if (f[i][j]){
ans++;
a.x = i; a.y = j;
ss.push(a);
while (!ss.empty()){
a = ss.front(); ss.pop();
f[a.x][a.y] = ;
for (int i = ; i <= ; ++i){
int x = a.x + dx[i], y = a.y + dy[i];
if (f[x][y]){ b.x = x; b.y = y; ss.push(b); }
}
}
}
cout << ans << endl;
}
上一篇:linux 设备驱动与应用程序异步通知


下一篇:iOS常见控件的基本使用