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

题目

描述

一矩形阵列由数字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 }