Lake Counting (POJ No.2386)

时间:2023-03-09 00:05:03
Lake Counting (POJ No.2386)

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

***

*W*

***

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