题解 P1451 【求细胞数量】

引领天下

2018-05-12 22:07:31

Solution

怎么楼下都是bfs啊…… 忍不住来了一发dfs 其实dfs也挺快的啊,0ms呢…… 思路也很简单,搞一个数组,不为0的地方就是细胞,然后dfs搜连通块,把搜到的都归0,保证不重复。。。 然后就是循环找没被归0的,答案+1。 代码: ```cpp #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; } ``` 好像挺简单的啊?