蓝桥杯：全球变暖

你有一张某海域NxN像素的照片，"."表示海洋、"#"表示陆地，如下所示：
.......
.##....
.##....
....##.
..####.
...###.
.......
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
.......
.......
.......
.......
....#..
.......
.......
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

【输入格式】
第一行包含一个整数N。 (1 <= N <= 1000)
以下N行N列代表一张海域照片。
照片保证第1行、第1列、第N行、第N列的像素都是海洋。

【输入样例】
7
.......
.##....
.##....
....##.
..####.
...###.
.......

【输出样例】
1

分析：有一种情况是一座岛屿部分淹没后变为两座岛屿，因此计算两遍岛屿数求差的做法是不对的。我的思路是，标记不被淹没的陆地（可以想象为岛屿上的“山”），无山的岛屿即是会被完全淹没的岛屿。
具体做法：标记完成后遍历map，从未被淹没的地块开始dfs岛屿，同时淹没经过的地块，若没有遇到过标记地块，则计数+1。

import java.util.Scanner;

public class Main8 {

    static boolean[][] map, map2;
    
    public static void main(String[] args) {
        //初始化地图，由于内存限制，用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用于标记不被淹没的陆地
        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;
    }

}