题解 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、输出找到的细胞数。 ```cpp #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; } } ```