一本通 1329

Robate · 2019-07-24 15:57:43 · 个人记录

以下是细胞个数的代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <stack>
#include <queue>
#define maxn 1010
using namespace std;

struct node{
    int x,y;
};
int n,m,cnt = 0;
int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};    // 方向数组
char mp[maxn][maxn];    // 用字符串保存地图
int check(int x,int y){     // 坚持坐标是否合法
    if(0 <= x && x < n && 0 <= y && y < m && mp[x][y] != '0') return 1;
    else return 0;
}

void bfs(int x,int y){
    queue<node> que;
    node a,t;       // 结构体的入队和基本数据的入队稍有不同
    t.x = x,t.y = y;
    que.push(t);
    while(!que.empty()){    // 如果队空，说明周围的数字都是零，可以结束本次搜索了
        a = que.front();que.pop();
        for (int i = 0;i < 4;++i){  // 查询每个点的上下左右四个方向
            int nx = a.x+dir[i][0],ny = a.y+dir[i][1];
            if(check(nx,ny)){
                t.x = nx,t.y = ny;
                que.push(t);
                mp[nx][ny] = '0';
            }
        }
    }
}

int main(){
    cin >> n >> m;
    for (int i = 0;i < n;i++){
        scanf("%s",mp[i]);
    }
    for (int i = 0;i < n;++i){
        for (int j = 0;j < m;++j){
            if(mp[i][j] != '0'){
                bfs(i,j);
                cnt++;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}