深度優先搜尋之水窪的數量

1. 問題描述：

水窪數目有一個大小為N * M的院子，雨後積起了水，

八連通的積水被認為是連在一起的，請求出園子裡面總共有多少水窪（八連通指的是下圖中相對w大的*部分）

***

*w*

***

限制條件

N, M <=100

樣例：

輸入

N = 10, M = 12

園子如下圖('W'表示積水，'.'表示沒有積水)

輸出3

2. 問題是要我們求解出連着的一片的水窪的數量，對于這類經典的問題，使用其它疊代等的方法是難以求解的，因為我們不知道連着的積水的區域有多少，對于這類問題的求解，我們是采用常用的無死角搜尋的深度優先搜尋dfs算法來解決，因為dfs能夠幫助我們搜尋出所有的可能，嘗試去走每一條路線，直到所有的路線都被走完了，那麼dfs久終止了

基于上面的分析，我們知道要使用dfs來求解，但是我們具體怎麼樣做呢，這裡假如從數組的起始位置開始上往下搜尋，那麼上一個狀從該數組的這個位置的八個方向開始搜尋，上一個狀态結束之後，那麼進入到下一個狀态，但是進入到下一個狀态的時候它也會往自己的八個方向開始搜尋，下一個狀态又會搜尋至上一個狀态的地方，而上一個狀态又會往下一個狀态搜尋，這就造成了遞歸無法出去了，永遠得不到答案而且會導緻棧溢出，是以我們該如何避免這種情況呢，其中比較有技巧的方法是當發現這個位置有積水之後把這個位置變為幹燥，即将字元'W'變為'.'，這樣轉移到下一個狀态的時候那麼往八個方向搜尋的時候就不會走之前有積水的地方，因為之前有積水的地方已經幹燥了，這樣問題就可以解決了，當一個dfs搜尋完之後那麼它周圍的積水都被清除掉了，那麼繼續尋找下一個有積水的地方然後進行dfs，當所有的積水區域都被趕走之後那麼水窪的數量就計算出來了

其中涉及到搜尋以自己為中心的八個方向的搜尋，是以存在着八個平行狀态的搜尋，這裡使用到了一個技巧就是使用兩層的for循環來進行處理

總結一下：比較核心的問題是如何避免在下一個狀态進入到上一個狀态的時候進入循環的遞歸，那麼這個時候就要将上一次的結果清除掉，這樣就不會陷入到無限遞歸的情況

3. 具體的代碼如下：

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int m = sc.nextInt();
		int n = sc.nextInt();
		int count = 0;
		char arr[][] = new char[m][n];
		for(int i = 0; i < m; i++){
			arr[i] = sc.next().toCharArray();
		}
		for(int i = 0; i < m; i++){
			for(int j = 0; j < n; j++){
				//有'W'的地方說明有積水
				if(arr[i][j] == 'W'){
					dfs(arr, i, j);
//					System.out.println(i + " " + j);
					count++;
				}
			}
		}
		System.out.println(count);
		sc.close();
	}

	private static void dfs(char[][] arr, int i, int j) {
		arr[i][j] = '.';
		//搜尋八個平行狀态然後看一下連通的水窪
		//因為涉及到八個平行狀态那麼可以使用for循環,但是我們可以使用嵌套兩個for循環的技巧來進行處理
		//因為加的都是-1 0 1 而1而且左上角到右下角
		//行的長度: arr.length 列的長度: arr[0].length
		for(int k = -1; k <= 1; k++){
			for(int l = -1; l <= 1; l++){
				if(k == 0 && l == 0) continue;
				if(i + k >=0 && j + l<= arr[0].length - 1 && i + k <= arr.length - 1 && j + l >=0){
					if(arr[i + k][j + l] == 'W'){
						//繼續搜尋它的下一個積水
						dfs(arr, i + k, j + l);
					}
				}
			}
		}	
	}
}