2.1.4 Lake Counting (POJ 2386) 深度搜索
我的思路:对每一个 'W' 进行处理,使与之挨着的 'W' 都替换 '.' ,然后递归,直至这个 'W' 周围的所有 'W' 都被替换成 '.' ,每进行上述操作一次,即有一个水洼存在,直至遍历所有的 'W'。
我的代码:
#include<stdio.h> #define MAX_N 110 #define MAX_M 110 int a[MAX_N][MAX_M]; int m,n; int dfs(int x,int y); int main(void) { int i,j,num=0; scanf("%d%d",&n,&m); for(i=0;i<n;i++) { getchar(); for(j=0;j<m;j++) { scanf("%c",&a[i][j]); } } for(i=0;i<n;i++) { for(j=0;j<m;j++) { if(a[i][j]=='W') { dfs(i,j); num++; } } } printf("%d\n",num); return 0; } int dfs(int x,int y) { if(x<0||x==n||y<0||y==m) { return 0; } if(a[x][y]=='.') { return 0; } a[x][y]='.'; return 1+dfs(x+1,y-1)+dfs(x,y-1)+dfs(x-1,y-1)+dfs(x+1,y)+dfs(x-1,y)+dfs(x+1,y+1)+dfs(x,y+1)+dfs(x-1,y+1); }
测试数据:
10 12 W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W.