题解P1451【求细胞数量】

发表于 | 更新于 | 评论数： | 阅读次数：
本文字数： 952 | 阅读时长 ≈ 1 分钟

一道可以用dfs做的题目（大佬勿喷）

总体思路如下：

  • 1 用一个bool数组存放每个位置是否为细胞数字

  • 2 输入，如果这个数大于0，把这个位置标记为1

  • 3 枚举每一个位置，如果是细胞数字就开始搜，同时答案加1

  • 4 输出

深搜部分：

  • 1 把这个位置标记为0

  • 2 枚举四个方向，如果是细胞数字就从这个位置继续搜

（就是把所有连通的细胞数字都标记为0，周围再也没有细胞数字了就代表一个细胞）

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
int n,m,sum;
char s;
bool p[110][110];
int a[4]={1,-1,0,0};//四个方向
int b[4]={0,0,-1,1};
void dfs(int x,int y) 
{
	p[x][y]=0;//把这个位置标记为0
	for(int i=0;i<4;i++)
	{
		int xx=x+a[i];
		int yy=y+b[i];
		if(p[xx][yy])//如果这个位置是细胞数字，从这个位置开始搜
		  dfs(xx,yy);
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	  {
	  	cin>>s;
	  	if(s>'0') p[i][j]=1;//是细胞数字标记为1
	  }
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	  {
	  	if(p[i][j])//如果是细胞数字开始搜
	  	{
	  		sum++;
	  		dfs(i,j);
		  }
	   } 
	printf("%d",sum);
	return 0;
}