首页 > 代码库 > 数细胞
数细胞
一矩形阵列由数字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();
}
}
#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();
}
}
数细胞
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。