DFS的八联通题：Lake Counting (POJ No.2386)

Lake Counting (POJ No.2386)

问题描述

有一个大小为NM的园子，雨后积起了水。八联通的积水被认为是连接在一起的。请求出园子里总共有多少水洼？（八联通指的是下图中相对W的的部分）

* * *
*W*
* * *

限制条件

N,M<=100

Sample

Input

N=10,M=12

W********WW*
*WWW*****WWW
****WW***WW*
*********WW*
*********W**
**W******W**
*W*W*****WW*
W*W*W*****W*
*W*W******W*
**W*********

Output

3

想法

从任意的W开始，不停地把邻接的部分用’*'代替。

1次DFS后与初始的这个W连接的所有W就都被替换成立’’，因此直到途中不再存在W为止，总共进行DFS的次数就是答案。8个方向共对应了8种状态转移，每个格子作为DFS的参数至多被调用一次，所以复杂的为O(8NM)=O(NM)

代码

//输入
int N,M;
char field[MAX_N][MAX_M+1];//现在位置(x,y)
void dfs(int x,int y){
    //将现在所在位置替换为*field[x][y]='*';//循环遍历移动的8个方向for(int dex=-1;dx<=1;dx++){
    for(itn dy=-1;dy<=1;dy++){
    //向x方向移动dx，向y方向移动dy，移动结果为(nx,ny)int nx=x+dx,ny=y+dy;//判断(nx,ny)是不是在园子内，以及是否有积水if(0<=nx&&nx<N&&0<=ny&&nu<M&&field[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(field[i][j]=='W'){
    //从有W的地方开始dfsdfs(i,j);res++;}}}cout<<res<<endl;
}