【题解】求细胞数量-C++

发布时间：2020-12-16 07:18:42 所属栏目：百科来源：网络整理

导读：题目描述一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。（1=m,n=100）? 输入输出格式输入格式：输入：整数m,n(m行，n列) 矩阵输出格式：输出：细胞的个数输入输出

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

输入输出格式
输入格式：
输入：整数m,n(m行，n列)

矩阵

输出格式：
输出：细胞的个数

输入输出样例
输入样例#1：
4 10
0234500067
1034560500
2045600671
0000000089
输出样例#1：
4

思路
这道题目实质上就是一个找连通块的问题，输入完成之后把整个矩阵遍历一遍，遇到不是0的就ans++，然后把它周围八个方块与它相同的全部改成0，直到没有再和它相同的为止。用搜索来做，广搜深搜都可以。

代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m;
 4 int ans;
 5 char a[105][105];
 6 void dfs(int x,int y)
 7 {
 8     if(x>n||x<1||y>m||y<1||a[x][y]==‘0‘)return;
 9     a[x][y]=‘0‘;
10     dfs(x+1,y);
11     dfs(x,y+1);
12     dfs(x-1,y);
13     dfs(x,y-1);
14 }
15 int main()
16 {
17     cin>>n>>m;
18     for(int i=1;i<=n;i++)
19     {
20         for(int j=1;j<=m;j++) cin>>a[i][j];
21     }
22     for(int i=1;i<=n;i++)
23     {
24         for(int j=1;j<=m;j++)
25         {
26             if(a[i][j]!=‘0‘)ans++,dfs(i,j);
27         }
28     }
29     cout<<ans<<endl;
30     return 0;
31 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!