题目描述：有一个大小为N*M的园子，八连通的积水被认为是连接在一起的。请求出园子里总共有多少水洼？（八连通指的是下图中相对w的*部分）
***
*w*
***
限制条件
N,M<=100
样例
输入：
N=10,M=12
园子如下图（'w'表示积水,'.'表示没有积水）
w . . . . . . . . ww .
. www . . . . www
. . . . ww . . . ww .
. . . . . . . . . . ww .
. . . . . . . . . . w . .
. . w . . . . . . . w . .
. w . w . . . . . ww .
w . w . w . . . . . w .
. w . w . . . . . . w .
. . w . . . . . . . . w .
输出
3
分析： 从图上可以直观的看出有三个连通块。从任意的w开始，不停的把邻接的部分用’ . '代替。1次dfs后 与初始的这个w连接的所有w就都被替换成了' . ',因此直到图中不再存在w为止，总共进行dfs的次数就是答案了。
#include<iostream>
using namespace std; #define MAX_N 101 int N,M;
int x1,x2,y1,y2;
char field[MAX_N][MAX_N+]; void dfs(int x,int y)//x,y为现在位置
{
field[x][y]='.';//将现在位置替换为'.'
x1=x-; x2=x+;
y1=y-; y2=y+; //向八个方向搜索
if(x1>= && field[x1][y]=='w') dfs(x1,y);
if(x2<N && field[x2][y]=='w') dfs(x2,y);
if(y1>= && field[x][y1]=='w') dfs(x,y1);
if(y2<M && field[x][y2]=='w') dfs(x,y2);
if(x1>=&&y1>=&&field[x1][y1]=='w') dfs(x1,y1);
if(x1>=&&y2<M&&field[x1][y2]=='w') dfs(x1,y2);
if(x2<N&&y1>=&&field[x2][y1]=='w') dfs(x2,y1);
if(x2<N&&y2<M&&field[x2][y2]=='w') dfs(x2,y2); return;
} int main()
{
cin>>N>>M;
for(int i=; i<N; i++){
for(int j=; j<M; j++)
{
cin>>field[i][j];
}
}
int res=;
for(int i=; i<N; i++){
for(int j=; j<M; j++){
if(field[i][j]=='w'){
dfs(i,j);
res++;
}
}
}
cout<<res;
return ;
}
其中函数dfs还有另一种写法
void dfs(int x,int y){
//将现在所在位置替换为.
field[x][y]='.';
//循环遍历移动的8个方向
for(int dx=-1;dx<=1; dx++){
for(int dy=-1; dy<1; dy++){
int nx=x+dx,ny=y+dy;
if(0<=nx && nx<N && 0<=ny && ny<M && field[nx][ny]=='w')
{
dfs(nx,ny);
}
}
}
return ;
}