题解 P1451 【求细胞数量】

· · 题解

1、从文件中读入m*n矩阵，将其转换为0、1矩阵存入a数组中；

2、沿a数组矩阵从上到下，从左到右，找到遇到的第一个细胞；将细胞的位置入队q，并沿其上、下、左、右四个方向上搜索，如果遇到细胞(a[i,j]=1)则将其位置入队，入队后的位置a[i,j]数组置为0；

3、将h队的队头出队，沿其上、下、左、右四个方向上搜索，如果遇到细胞则将其位置入队，入队后的位置a数组置为0；

4、重复3，直至h队空为止，则此时找出了一个细胞；

5、重复2，直至矩阵找不到细胞；

6、输出找到的细胞数。

#include<iostream>  
#include<cstring>  
#include<queue>  
#include<cstdio>  
using namespace std;  
const int gx[4]={0,0,-1,1};  
const int gy[4]={1,-1,0,0};  
int m,n,tot=0;  
bool 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<<tot<<endl;  
    return 0;  
}  
void work(int x,int y)  
{  
    queue<int> qx,qy;//两队列分别存储当前点的行和列   
    int x1,y1;  
    tot++;//细胞数加一   
    qx.push(x);//把当前细胞的行和列入队   
    qy.push(y);  
    a[x][y]=0;//当前细胞因为已计算，赋为false   
    while(!qx.empty())//当队列非空   
    {  
        for(int i=0;i<4;i++)//对当前细胞的上下左右进行搜索   
        {  
            x1=qx.front()+gx[i];  
            y1=qy.front()+gy[i];  
            if(x1>0&&x1<=m&&y1>0&&y1<=n&&a[x1][y1])  
            {  
                qx.push(x1);//如果没有越界且（x1,y1）为细胞 ，入队   
                qy.push(y1);  
                a[x1][y1]=false;   
            }  
        }  
        qx.pop();//for循环结束，a[x][y]相邻细胞处理完成，则将其出队   
        qy.pop();  
    }  
}  
void init()  
{  
    string s;  
    cin>>m>>n;  
    for(int i=1;i<=m;++i)  
    {  
        cin>>s;   
        for(int j=0;j<n;++j)  
          if(s[j]=='0')a[i][j+1]=0;  
          else a[i][j+1]=1;  
    }  
}