为了做好apple tree。。我先水个dfs的题吧。。。这个题确实挺水的T_T,就是一裸裸的dfs啊。。。。结果一开始还卡在了输入上。。。。
题意就是给你一个char的数组,求有多少个连通分量。
典型的dfs。。【递归的比较水的说。。。。ps后来知道可以用bfs做。。。。哪天做到bfs再重新把题做一遍好了。。。
#include <cstdio> #include <cstring> using namespace std; const int maxn=105; int ans=0,m,n; char deposit[maxn][maxn]; void dfs(int x,int y) { if(x<0||x>=m||y<0||y>=n||deposit[x][y]!='@') return; deposit[x][y]='*'; dfs(x-1,y); dfs(x,y-1); dfs(x+1,y); dfs(x,y+1); dfs(x+1,y+1); dfs(x+1,y-1); dfs(x-1,y-1); dfs(x-1,y+1); } int main() { while(scanf("%d%d",&m,&n),m) { ans=0; for(int i=0;i<m;i++) { scanf("%s",&deposit[i]); } for(int i=0;i<m;i++) for(int j=0;j<n;j++) { if(deposit[i][j]=='@') { ans++; dfs(i,j); } } printf("%d\n",ans); } }