题目链接:点击打开链接

中文题目参考《挑战程序设计竞赛-第2版》

算法核心内容:遍历整个"园子数组",从园子的某一块填充的是“W”时,对该块地进行搜索(上下左右,以及斜对角八个方向),(注意把这块地填充的‘w’换成“.”,避免后面搜索重复),如果这八块地方中还存在填充的是“W”的地,就继续重复上面的操作,直到所有“w”全部换成“.”,说明周围都是空地了,没有相连的水洼了。如图。

把相邻所有的“W”换成“.”的次数,即为答案。

#include<cstdio>
const int MAX=105;
int N,M;
char field[MAX][MAX];   //二维“园子数组”
void dfs(int x,int y){
field[x][y]='.';      //找到“w”,先替换为.,避免后面搜索重复;
for(int dx=-1;dx<=1;dx++){
for(int dy=-1;dy<=1;dy++){
int nx=x+dx;
int ny=y+dy;

if(0<=nx&&nx<N&&0<=ny&&ny<M&&field[nx][ny]=='W')

                         dfs(nx,ny);

//判断当前坐标,没出格并且当前坐标填充的还是W,就继续进行

}
}
  return ;
}
void solve(){
int ans=0;
for(int i=0;i<N;i++)
{
for(int j=0;j<M;j++)
{
if(field[i][j]=='W')
{  
  dfs(i,j);//一大块整个的水洼搜索完毕,退出dfs.
  ans++;//水洼总数+1;
}
}
}
printf("%d\n",ans);
}
int main(){
int p,q;
scanf("%d%d",&N,&M);
for(p=0;p<N;p++){
for(q=0;q<=M;q++){
scanf("%c",&field[p][q]);

}

  getchar();

}
solve(); 
return 0;
}