P1451 求细胞数量(广搜)

时间:2022-08-30 08:12:11

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

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

#include<iostream>
#include<queue>
using namespace std;

const int maxn = 110;

struct node{
    int x, y;
}a, b;
bool f[maxn][maxn];
char s[maxn];
int dx[5] = { 0, 0, 0, 1, -1 };
int dy[5] = { 0, -1, 1, 0, 0 };
int n, m, ans;
int tail, head;
queue<node>ss;

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; ++i){
        cin >> s;
        for (int j = 0; s[j];++j)
        if (s[j] != '0'){
            f[i][j + 1] = 1;
        }
    }
    for (int i = 1; i <= n;++i)
    for (int j = 1; 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] = 0;
            for (int i = 1; i <= 4; ++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;
}