1329细胞

1329细胞

编程基础 • 2024-12-05 17:17 • 阅读 8

题目

原题链接http://ybt.ssoier.cn:8088/problem_show.php?pid=1329

【题目描述】

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

阵列

4 10 0   0000000089

有44个细胞。

【输入】

第一行为矩阵的行n和列m;

下面为一个n×m的矩阵。

【输出】

细胞个数。

【输入样例】

4 10 0   0000000089

【输出样例】

分析

注意到这道题数据为一整行，没有空格，所以用int类型输入显然是不行的，我们可以用char类型的二维数组来输入。整体思路为广度优先搜索，这道题就是一个模板。

思路

首先创建全局变量、数组、以及结构体。代码如下：

int n,m; int s[4][2]={ 
  {1,0},{0,1},{-1,0},{0,-1}};//偏移量数组 char a[1000][1000]; int mk[1000][1000];//标记数组 int res=0;//记个数 struct node{ int x;//x坐标 int y;//y坐标 };

然后写bfs广搜函数。详解见如下代码注释：

void bfs(int x,int y){ queue<node>q;//结构体队列 q.push((node){x,y}); //入队 while(q.size()){ node t=q.front();//出队 q.pop();//删除 for(int i=0;i<4;i++){ int xx=t.x+s[i][0]; int yy=t.y+s[i][1]; if(xx>=0&&xx<n&&yy>=0&&yy<m&&mk[xx][yy]==0&&a[xx][yy]!='0'&&a[xx][yy]<='9'){ mk[xx][yy]=1;//标记 q.push((node){xx,yy});//入队 } } } }

接着写主函数里的输入。代码如下：

cin>>n>>m; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>a[i][j]; } }

输入完之后循环调用bfs函数。

for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(a[i][j]!='0'&&mk[i][j]==0){ res+=1; mk[i][j]=1; bfs(i,j); } } }

最后输出res。

cout<<res<<endl;

完整代码

#include<iostream> #include<queue> using namespace std; int n,m; int s[4][2]={ 
  {1,0},{0,1},{-1,0},{0,-1}}; char a[1000][1000]; int mk[1000][1000]; int res=0; struct node{ int x; int y; }; void bfs(int x,int y){ queue<node>q; q.push((node){x,y}); while(q.size()){ node t=q.front(); q.pop(); for(int i=0;i<4;i++){ int xx=t.x+s[i][0]; int yy=t.y+s[i][1]; if(xx>=0&&xx<n&&yy>=0&&yy<m&&mk[xx][yy]==0&&a[xx][yy]!='0'&&a[xx][yy]<='9'){ mk[xx][yy]=1; q.push((node){xx,yy}); } } } } int main(){ cin>>n>>m; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>a[i][j]; } } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(a[i][j]!='0'&&mk[i][j]==0){ res+=1; mk[i][j]=1; bfs(i,j); } } } cout<<res<<endl; return 0; }

新手上路，请多多指教。

今天的文章 1329细胞分享到此就结束了，感谢您的阅读。

题目