【題解】Luogu p1451 【求细胞数量】BFS大禮包系列

這題是本人BFS40題大禮包的第一題
題目沒啥難的
只是輸入非常坑了

請注意:Windows與Linux的換行不同,win為\n,lin為\r\n,在處理輸入的情況下吸收空格時是吸兩次。
第一行那兩個數後面也得吸掉換行(如果你是用%c讀入的話)。
其他沒啥好說的。
就是一個bfs上下左右。
這題好像還可以建隱式圖,然後就連通分量個數。

#include<cstdio>
#include<queue>

const int L = 100 + 6;
bool map[L][L];
int ans = 0,m,n;

const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,1,-1};

class Point{
    public:int x,y;

    public:Point(int y,int x){
        this -> y = y;
        this -> x = x;
    }
};

void read(int m,int n){
    char ggg,gg;
    for(int i = 0;i < m;i++){
        for(int j = 0;j < n;j++){
            scanf("%c",&ggg);
            if(ggg != '0'){
                map[i][j] = true;
            }else{
                map[i][j] = false;
            }
        }
        scanf("%c",&gg);
        scanf("%c",&gg);
    }
}

void naive(int y,int x){
    ans++;
    std::queue<Point> Q;
    Q.push(Point(y,x));
    map[y][x] = false;

    while(Q.size()){            
        for(int i = 0;i < 4;i++){
            int nx = Q.front().x + dx[i];
            int ny = Q.front().y + dy[i];

            if(nx >= 0 && ny >= 0 && nx < n && ny < m && map[ny][nx] == true){
                Q.push(Point(ny,nx));
                map[ny][nx] = false;
            }
        }
        Q.pop();
    }
}

int main(){
    scanf("%d %d\n",&m,&n);

    read(m,n);

    for(int i = 0;i < m;i++){
        for(int j = 0;j < n;j++){
            if(map[i][j]){
                naive(i,j);
            }
        }
    }
    printf("%d",ans);

    return 0;
} 

/*样例数据 
in:1
4 10
0234500067
1034560500
2045600671
0000000089
out:1
4

in:2
10 10
1111111111
0000000000
1111111111
0000000000
1111111111
0000000000
1111111111
0000000000
1111111111
0000000000
out:2
5
*/