p1451 求细胞数量

题目描述

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

输入输出格式

输入格式:

 

输入:整数m,n(m行,n列)

矩阵

 

输出格式:

 

输出:细胞的个数

。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

 

你可能没看懂题目中什么是细胞?

解释一下(本蒟蒻的理解):你可以想象你用一个扫描器扫描一个显微镜下的细胞装片,上面有好多细胞,有细胞的区域有颜色,扫描器上的像素就会返回不是0的值,如果此像素区域内没有细胞,那么颜色为透明的,就返回0(有颜色的数值对应不同颜色(不用管哪个颜色只要有就行))。那么我们要求的就是有几块有颜色(数值)的区域

题目样例共有4块非零数字群(4块细胞。。)那么有4个。

怎么查?

很简单,从第一行开始找,找到非零的就把细胞数(sum)+1,然后把与这个数(像素)连着的非零数(像素内有细胞的区域)筛掉就行了。  相当于找到一个细胞就去掉!(怎么将粘在一起的数值筛掉是个问题)

去掉的过程用广度搜索,具体看代码:

AC代码上:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int m,n,jz[102][102],sum=0;
char jz1[102];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
void xibao(int i,int j)
{
    int h[10002][2],t=0,w=1,x,y;//h为队列,用来存细胞的每个坐标
    sum++;jz[i][j]=0;//把当前扫到的像素置为零
    h[1][1]=i;h[1][2]=j;存入当前像素坐标
    do{
        t++;//t为tou(头)指队列头元素
        for(int i=0;i<=3;i++)
        {
            x=h[t][1]+dx[i];y=h[t][2]+dy[i];//dy和dx存的是上下左右移动的坐标改变量,x,y为当前搜索的坐标
            if((x>=0)&&(x<m)&&(y>=0)&&(y<n)&&(jz[x][y]==1))//前四个为矩阵上下左右的界,判断是否因为上下左右查找而出界
            {
                w++;//w就是wei(尾)指队尾
                h[w][1]=x;h[w][2]=y;//在队列尾部存下来坐标
                jz[x][y]=0;//重置0(关键!可以保证一个细胞不被重复查找,我第一次编译时就忘了)
            }
        }
    }while(t<w);//当队列中还有元素时还有
}
int main(){
    cin>>m>>n;
    for(int i=0;i<m;i++)
        {
            scanf("%s",jz1);//为何要用字符串输入?因为这样可以判断是否有颜色(有数值),因为他输入是连着无空格的嘛QWQ
            for(int j=0;j<n;j++)
                if(jz1[j]!='0')jz[i][j]=1;//有数值的都一样(等价)把他们都搞成1,和0区分开就行了,不然还会麻烦点。。
        }
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)
        {
            if(jz[i][j]==1)//找到了一个有细胞的像素
            {
                xibao(i,j);//那么开始从矩阵中删除这个细胞
            }
        }
    printf("%d",sum);//输出和就行了
    return 0;
}

 完结撒花✿ヽ(°▽°)ノ✿

上一篇:102. 二叉树的层次遍历


下一篇:102、灭火器的配置要求