你有一張某海域NxN像素的照片偿短，"."表示海洋、"#"表示陸地馋没，如下所示：
.......
.##....
.##....
....##.
..####.
...###.
.......
其中"上下左右"四個方向上連在一起的一片陸地組成一座島嶼翔冀。例如上圖就有2座島嶼。
由于全球變暖導(dǎo)致了海面上升披泪，科學(xué)家預(yù)測未來幾十年纤子，島嶼邊緣一個像素的范圍會被海水淹沒。具體來說如果一塊陸地像素與海洋相鄰(上下左右四個相鄰像素中有海洋)款票，它就會被淹沒控硼。
例如上圖中的海域未來會變成如下樣子：
.......
.......
.......
.......
....#..
.......
.......
請你計算：依照科學(xué)家的預(yù)測，照片中有多少島嶼會被完全淹沒卡乾。
【輸入格式】
第一行包含一個整數(shù)N谍椅。 (1 <= N <= 1000)
以下N行N列代表一張海域照片。
照片保證第1行、第1列、第N行、第N列的像素都是海洋。
【輸入樣例】
7
.......
.##....
.##....
....##.
..####.
...###.
.......
【輸出樣例】
1
分析：有一種情況是一座島嶼部分淹沒后變?yōu)閮勺鶏u嶼力图，因此計算兩遍島嶼數(shù)求差的做法是不對的吕喘。我的思路是，標(biāo)記不被淹沒的陸地（可以想象為島嶼上的“山”），無山的島嶼即是會被完全淹沒的島嶼辕漂。
具體做法：標(biāo)記完成后遍歷map鲸阻，從未被淹沒的地塊開始dfs島嶼，同時淹沒經(jīng)過的地塊性置，若沒有遇到過標(biāo)記地塊，則計數(shù)+1之碗。
import java.util.Scanner;
public class Main8 {
static boolean[][] map, map2;
public static void main(String[] args) {
//初始化地圖博敬，由于內(nèi)存限制偏窝，用bit表示海洋或陸地
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.nextLine();
map = new boolean[n][n];
for(int i=0; i<n; ++i)
{
String s = sc.nextLine();
for(int j=0; j<n; ++j)
{
if(s.charAt(j)=='.')
map[i][j]=false;
else
map[i][j]=true;
}
}
sc.close();
//map2用于標(biāo)記不被淹沒的陸地
map2 = new boolean[n][n];
for(int i=0; i<n; ++i)
for(int j=0; j<n; ++j)
map2[i][j] = false;
for(int i=0; i<n; ++i)
for(int j=0; j<n; ++j)
if(map[i][j])
if(map[i-1][j]&&map[i+1][j]&&map[i][j-1]&&map[i][j+1])
map2[i][j]=true;
int cnt=0;
for(int i=0; i<n; ++i)
for(int j=0; j<n; ++j)
if(map[i][j])
cnt+=dfs(i,j)?1:0;
System.out.print(cnt);
}
public static boolean dfs(int i, int j)
{
boolean flag = true;
map[i][j]=false;
if(map2[i][j])
flag = false;
if(map[i-1][j]) flag &= dfs(i-1, j);
if(map[i+1][j]) flag &= dfs(i+1, j);
if(map[i][j-1]) flag &= dfs(i, j-1);
if(map[i][j+1]) flag &= dfs(i, j+1);
return flag;
}
}
