水窪數目

題目: 有一個大小為N*M的園子, 雨後起了積水，八連通的積水被認為是連接配接在一起的。請求出園子裡總共有多少水窪.如下列字元組成的圖,可以看出有兩個水窪。

使用深度優先搜尋(DFS), 在某一處水窪, 從8個方向查找, 直到找到所有連通的積水. 再次指定下一個水窪, 直到沒有水窪為止。

輸入資料:
5 5
...WW
WWWW.
...W.
W....
WWW..

public class dfs_水窪數目 {
    static int M,N;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        M = sc.nextInt();
        N = sc.nextInt();
        char[][] arr = new char[M][N];
        for(int i=0;i<M;i++) {
            arr[i] = sc.next().toCharArray();
        }
        int count = 0;
        for(int i=0;i<M;i++) {
            for(int j=0;j<N;j++) {
                if(arr[i][j]=='W') {
                    dfs(arr,i,j);//清除一個水窪
                    count++;
                }
            }
        }
        System.out.println(count);
    }
    
    
    static void dfs(char[][] A,int i,int j) {
        A[i][j] = '.';
        //對八個方向進行移動,即使i/j分别加上-1,0,1   特别的,當i/j分别加上0時此點不移動
        for(int x = -1;x<=1;x++) {
            for(int y = -1;y<=1;y++) {
                if(x == 0 && y == 0)  continue;//除去本點
                if(i+x>=0 && i+x<M && j+y>=0 &&  j+y<N) {//對某個點的八個方向進行周遊
                    if(A[i+x][j+y] ==  'W')dfs(A,i+x,j+y);
                }
            }
        }
    }
}
           

最後，請你熟記八個方向周遊的技巧，因為很多路徑類的算法題都可以使用這個技巧。