题目大意

有一个大小为 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

分析

此类问题 适合dfs。
采用深度优先搜索，从任意的w开始，不断把邻接的部分用'.'代替，1次DFS后与初始这个w连接的所有w就全都被替换成'.'（为了防止回溯搜索导致死循环，把已经扫到的洼地的水抽干），因此直到图中不再存在W为止，总共进行DFS的次数就是答案。8个方向对应8个状态转移，每个格子作为DFS的参数最多调用一次，因时间复杂度为O(8nm)=O(nm)。
其中的状态转移写法比较妙~

代码

package BlueCup.Seven_recursion;

import java.util.Scanner;

public class Dfs3水洼的数目 {
    static int n,m;
    public static void main(String[] args) {
        Scanner cin =new Scanner(System.in);
         n=cin.nextInt();
         m=cin.nextInt();
        char [][] a=new char[n][];
        int cnt=0;
        for (int i = 0; i < n; i++) {
            a[i]=cin.next().toCharArray();
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(a[i][j]=='W') {
                    dfs(a, i, j);//清除一个水洼
                    cnt++;//计数
                }

            }
        }
        System.out.println(cnt);

    }

    private static void dfs(char[][] a, int i, int j) {
        a[i][j]='.';
        for (int k = -1; k <2 ; k++) {//-1 0 1  9种状态
            for (int l = -1; l <2 ; l++) {

                if(k==0&&l==0){ //不动的状态去除
                    continue;
                }
                if(i+k>=0&&i+k<=n-1&&j+l>=0&&j+l<=m-1){//边界检测 行 列 八个平行状态
                    if(a[i+k][j+l]=='W'){
                        dfs(a,i+k,j+l);
                    }
                }
            }
        }
    }
}