1329：【例8.2】细胞

时间限制: 1000 ms         内存限制: 65536 KB

【题目描述】

4 10
0234500067
1034560500
2045600671
0000000089

【输入】

【输出】

【输入样例】

4 10
0234500067
1034560500
2045600671
0000000089

【输出样例】

4

解析：广度优先搜索算法，遍历矩阵中所有位置，从非零位置开始广度优先搜索，针对四个方向，对于搜索到的细胞位置清零，得到答案。

详见代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[1005][1005];//矩阵
int ans=0;//答案
queue <int> qx;//x坐标队列
queue <int> qy;//y坐标队列
int dx[4]={0,0,1,-1};//四个方向
int dy[4]={1,-1,0,0};
void bfs(int x,int y){//从xy位置开始广度优先搜索
    a[x][y]='0';//清0
    qx.push(x);//起点入队
    qy.push(y);
    while (!qx.empty()){//只要队列非空
        int xx=qx.front();//取队首坐标xy
        qx.pop();
        int yy=qy.front();
        qy.pop();
        for(int i=0;i<4;i++){//四个方向搜索
            int xxx=dx[i]+xx;
            int yyy=dy[i]+yy;
            if (a[xxx][yyy]!='0'&&a[xxx][yyy]!=0){//不是‘0’并且不出界（0）
                a[xxx][yyy]='0';
                qx.push(xxx);//入队
                qy.push(yyy);
            }
        }
    }
}
int main() {
    cin>>n>>m;
    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]!='0'){//从不是‘0’的位置开始搜索
                ans++;//答案加一
                bfs(i,j);
            }
        }
    }
    cout<<ans;
    return 0;
}