7.6 dfs競賽例題---水窪數（經典題！最後背下！）

import java.util.Scanner;

public class Main {

	/*思路：
	 * （1）從頭開始進行周遊，尋找第一個積水W
	 *    （1.1）從該處進行dfs周遊，
	 *           尋找其8個方向是否有積水W，如果存在将其改為陸地.（避免重複通路）， 繼續進行周遊。
	 *    （1.2）每完成一次dfs周遊，就周遊完了一片水窪
	 *           對水窪進行計數
	 *注意：
	 *  （1）為了避免重複通路，每周遊完一個積水W，就将其改為陸地.
	 *  （2）通路8個方向時，可借助雙層for循環
	 * 
	 * 測試資料
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
	 * */
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();//行
		int m=sc.nextInt();//列
		char[][] a = new char[n][];//積水陸地表。W積水  .沒有積水
		for(int i=0;i<n;i++) {
			a[i]=sc.next().toCharArray();
		}
		//（1）尋找目前第一個水窪W
		int cnt=0;//記錄水窪總數
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(a[i][j]=='W') {
					dfs(a,i,j); //從a[i][j]處進行dfs周遊
					cnt++;
				}
			}
		}
		System.out.println(cnt);
	}

	private static void dfs(char[][] a, int i, int j) {
		//（1）先将目前通路的積水W 改為 陸地.
		a[i][j]='.';
		//(2)通路a[i][j]8個方向(分别對i和j進行-1、+1、+0)
		for(int l=-1;l<=1;l++) {//l和h分别表示坐标i，j累加的量(橫坐标)
			for(int h=-1;h<=1;h++) {//（縱坐标）
				if(l==0&&h==0) continue; //方向沒有發生變化
				if(i+l>=0 && i+l<=a.length-1 && j+h>=0 && j+h<=a[0].length-1) {
					if(a[i+l][j+h]=='W') {//注意：隻有下一個位置是積水時，才進行通路
						dfs(a,i+l,j+h);
					}
				}//if
			}//for
		}//for
		
	}
	
}