题解 P1451 【求细胞数量】

发表于 更新于 阅读次数： Waline：
P1451 【求细胞数量】题解。

怎么楼下都是bfs啊……

忍不住来了一发dfs

其实dfs也挺快的啊，0ms呢……

思路也很简单，搞一个数组，不为0的地方就是细胞，然后dfs搜连通块，把搜到的都归0，保证不重复。。。

然后就是循环找没被归0的，答案+1。

代码：

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
#include <bits/stdc++.h>
using namespace std;
template <typename _Tp>
inline void read(_Tp &x){
    int w=1;char c=0;x=0;
    while (c^'-'&&(c<'0'||c>'9'))c=getchar();
    if (c=='-')w=-1,c=getchar();
    while (c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x*=w;
}
inline void write(int n){
    if(n==0) return;
    write(n/10);
    putchar(n%10+'0');
}//输入输出优化，请自动忽略
int n,m,ans,dx[]={-1,0,1,0},dy[]={0,-1,0,1},a[105][105];//a即地图，dx和dy方向增量数组就不用我讲了吧
void dfs(int x,int y){
	if (x>n||y>m||x<0||y<0)return;
	a[x][y]=0;//标记为没有
	for (int i=0;i<4;i++)if (a[x+dx[i]][y+dy[i]])dfs(x+dx[i],y+dy[i]);//如果有才搜
}//搜索
int main(){
	read(n),read(m);
	for (int i=0;i<n;i++)
	for (int j=0;j<m;j++)scanf("%1d",&a[i][j]);//只读1位
	for (int i=0;i<n;i++)
	for (int j=0;j<m;j++)if (a[i][j])ans++,dfs(i,j);//找
	write(ans);//输出
	return 0;
}

好像挺简单的啊？