Lake Counting (POJ No.2386)

Lake Counting (POJ No.2386)

有一个大小为N*M的园子，雨后积起了水，八连通的积水被认为是链接在一起的求出园子里一共有多少水洼？

***

*W*

***

/**
*进行深度优先搜索，从第一个W开始，将八个方向可以到达的 W修改为 .
*每次进行深度优先搜索的时候就将链接的水坑换成了.
*进行的深度优先搜索的次数就是水坑数 
*/
#include<stdio.h>
#include<string.h>
const int  MAX=100; 
int N,M;
char filed[MAX][MAX];  //园子的构造 
//现在的位置（x,y）
void dfs(int x,int y){//将现在所在的位置替换为‘.’filed[x][y]='.';//循环遍历移动的8个方向for(int dx=-1;dx<=1;dx++){for(int dy=-1;dy<=1;dy++){int nx=x+dx,ny=y+dy;//判断（nx,ny是不是在园子内，以及是否有积水）if(0<=nx && nx<N && 0<=ny && ny<M && filed[nx][ny]=='W')dfs(nx,ny); }} return;
} 
void solve(){int res=0;for(int i=0;i<N;i++)for(int j=0;j<M;j++){if(filed[i][j]=='W'){dfs(i,j);      //从有积水的地方开始遍历，遍历的次数就是水坑的个数 res++;}}printf("%dn",res);
}
int main(){while(scanf("%d%d",&N,&M)==2){getchar();for(int i=0;i<N;i++)for(int j=0;j<M;j++)scanf("%c",&filed[i][j]);solve();}return 0;
} 

转载于:.html