你好呀，我是灰小猿，一個超會寫bug的程式猿！

歡迎大家關注我的專欄“每日藍橋”，該專欄的主要作用是和大家分享近幾年藍橋杯省賽及決賽等真題，決議其中存在的演算法思想、資料結構等內容，幫助大家學習到更多的知識和技術！

標題：全球變暖

你有一張某海域 N×N像素的照片，”.”表示海洋、”#”表示陸地，如下所示：

其中”上下左右”四個方向上連在一起的一片陸地組成一座島嶼，例如上圖就有 2座島嶼，由于全球變暖導致了海面上升，科學家預測未來幾十年，島嶼邊緣一個像素的范圍會被海水淹沒，

具體來說如果一塊陸地像素與海洋相鄰(上下左右四個相鄰像素中有海洋)，它就會被淹沒，

例如上圖中的海域未來會變成如下樣子：

請你計算：依照科學家的預測，照片中有多少島嶼會被完全淹沒，

輸入格式

第一行包含一個整數N，

以下 N行 N 列，包含一個由字符”#”和”.”構成的 N×N字符矩陣，代表一張海域照片，”#”表示陸地，”.”表示海洋，照片保證第 1行、第 1 列、第 N 行、第 N列的像素都是海洋，

輸出格式

一個整數表示答案，

資料范圍

1≤N≤1000

輸入樣例1：

7

.......

.##....

.##....

....##.

..####.

...###.

.......

輸出樣例1：

1

輸入樣例2：

9

.........

.##.##...

.#####...

.##.##...

.........

.##.#....

.#.###...

.#..#....

.........

輸出樣例2：

1

資源約定: .

峰值記憶體消耗(含虛擬機) < 256M

CPU消耗< 1000ms

請嚴格按要求輸出，不要畫蛇添足地列印類似:“ 請您輸...”的多余內容.

所有代碼放在同-一個源檔案中，除錯通過后，拷貝提交該原始碼.

不要使用package陳述句，不要使用jdk1.7及以上版本的特性，

主類的名字必須是: Main, 否則按無效代碼處理.

解題思路

本題在求解的時候其實主要就是判斷有哪幾個陸地是在同一個島嶼上的，其實就是二維陣列連通塊的判斷問題，判斷出有哪幾個塊是共同組成了一個島嶼之后，很多同學可能會想著看看每一塊是否是靠海的，其實這樣的解決原則是沒有問題的，但是具體在實踐的程序中其實是不好解決的，

所以我們可以直接在判斷該塊是否是與其他塊連通的時候，就可以判斷該陸地塊的周圍是不是海洋，我們可以定義兩個變數，cnt1表示該島嶼所有陸地的數量，cnt2表示該島嶼上靠海陸地的數量，在找完該島嶼上所有的陸地塊之后，我們判斷所有陸地數量和靠海陸地數量是否相等，即cnt1是否等于cnt2，如果等于，則說明所有陸地都是靠海的，那么該島嶼一定會被淹沒，

至于連通塊的判斷，其實是使用了BFS廣度搜索的思路，每走過一個區域，就標記該區域不能再走，直到走完所有的塊為止，

答案原始碼：

package 一八年省賽真題;

import java.awt.Point;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Year2018_Bt9 {

	static int N;
	static int[][] mark;
	static char[][] mapData;
	static int ans=0;
	static int[] tox = {-1,0,1,0};
	static int[] toy = {0,1,0,-1};
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		N = scanner.nextInt();
		scanner.nextLine();
		mark = new int[N][N];
		mapData = new char[N][N];
		
		for (int i = 0; i < N; i++) {
			String info = scanner.nextLine();
			mapData[i] = info.toCharArray();
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				//如果該點是陸地且未被訪問
				if (mapData[i][j]=='#' && mark[i][j]==0) {
					bfs(i,j);
				}
			}
		}
		System.out.println(ans);
	}
	
	/**廣度優先搜索演算法
	 * 遍歷連通塊
	 * */
	private static void bfs(int x, int y) {
		mark[x][y] = 1;	//表示該點已經訪問過
		int cnt1 = 0;	//表示總陸地數
		int cnt2 = 0;	//表示靠近海洋的陸地數
		
		Queue<Point> queue = new LinkedList<Point>();//建立佇列，存放一個點類
		queue.add(new Point(x, y));
		//如果佇列不為空
		while(!queue.isEmpty()) {
			Point point = queue.poll();	//取出佇列頭元素
			boolean isKaoHai = false;	//表示該塊陸地靠海
			cnt1++;
			
			//遍歷四個方向
			for (int i = 0; i < 4; i++) {
				int newx = point.x + tox[i];
				int newy = point.y + toy[i];
				if(mapData[newx][newy]=='.') isKaoHai = true;
				//如果相鄰的是陸地，且未被探索
				if (mapData[newx][newy]=='#' && mark[newx][newy]==0) {
					queue.add(new Point(newx, newy));//將新的陸地加入佇列					
					mark[newx][newy] = 1;
				}
			}
			if (isKaoHai) cnt2++;	//如果靠海，則靠海的陸地數量加一
		}
		//如果靠海的陸地數和總的陸地數相等，則島嶼全部淹沒
		if (cnt1==cnt2) ans++;
	}

}