首页 > 代码库 > 数细胞

数细胞

一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。

第一行输入两个整数,分别代表矩阵的行和列 输入m*n的矩阵,由数字0到9组成。

输入:

4 10
1 2 3 4 5 1 1 1 6 7 
1 0 3 4 5 6 1 5 1 0
2 0 4 5 6 6 1 6 7 1
0 0 6 0 6 6 1 0 8 9
输出:
1
代码:
#include<iostream>
#include<queue>
using namespace std;
const int gx[4]={0,0,-1,1};
const int gy[4]={1,-1,0,0};
int m,n,total=0;
int a[110][110];
void init();
void work(int,int );
int main()
{
    init();
    for(int i=1;i<=m;i++)   //枚举整个m*n的矩阵
        for(int j=1;j<=n;j++)
            if(a[i][j])
                work(i,j);  //找到一个细胞,并对该细胞进行处理
    cout<<total;
    return 0;
}
void init()
{
    cin>>m>>n;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
                cin>>a[i][j];
}
void work(int x,int y)
{
    queue<int>qx,qy;//两个队列分别储存当前点的行与列
    total++;
    int xx,yy;
    qx.push(x);//把当前细胞的行和列入队
 qy.push(y);
 a[x][y] = 0;//当前细胞因为已计算,赋为false
    while(!qx.empty())//当队列不为空
    {
        for(int i=0;i<4;i++)
        {
            xx=qx.front()+gx[i];
            yy=qy.front()+gy[i];
            //如果没有越界,并且(xx,yy)是细胞,入队
            if(xx>0 && xx <= m && yy>0 && yy <= n && a[xx][yy])
            {
                qx.push(xx);
                qy.push(yy);
                a[xx][yy] = 0;
            }
        }
        //for循环结束,a[x][y]相邻细胞处理完成,将其出队
        qx.pop();
        qy.pop();
    }
}

数细胞