1329：【例8.2】细胞

传送门：http://ybt.ssoier.cn:8088/problem_show.php?pid=1329

【题目描述】

一矩形阵列由数字 $0$

到 $9$ 组成,数字 $1$ 到 $9$

代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如:

阵列

有 $4$

个细胞。

【输入】

第一行为矩阵的行 $n$

和列 $m$

;

下面为一个 $n \times m$

的矩阵。

【输出】

细胞个数。

【输入样例】

【输出样例】

#include<iostream>
#include<queue>
#include<cstring>
using namespace std; 
#define N 100
struct qs{
    int x,y;
};
int n,m,ans;
char map[N][N];
bool maps[N][N];
int xs[]={0,0,-1,1};
int ys[]={1,-1,0,0};
queue < qs >q;
int main()
{
    cin>>n>>m;
    memset(maps,false,sizeof(maps));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>map[i][j];
            if(map[i][j]!='0')maps[i][j]=true;
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(maps[i][j]==true)
            {
                // maps[i][j]=f
                qs tmp;
                tmp.x=i;tmp.y=j;
                q.push(tmp);
                while(!q.empty())
                {
                    qs tmp1=q.front();
                    q.pop();
                    for(int ks=0;ks<4;ks++)
                    {
                        int x1,y1;
                        x1=tmp1.x+xs[ks];
                        y1=tmp1.y+ys[ks];
                        if(maps[x1][y1]==true&&x1>=1&&x1<=n&&y1<=m&&y1>=1)
                        {
                            qs df;
                            df.x=x1;
                            df.y=y1;
                            maps[x1][y1]=false;
                            q.push(df);
                        }
                    }
                }
                ans++;
            }
        }
    cout<<ans<<endl;
}