蓝桥杯2018年第九届真题-全球变暖-JAVA【参考优质题解】-详细注释

定义静态全局变量：
visited数组标记当前点是否被访问；
map表示地图；
dx，dy分别表示x，y进行上下左右偏移时的偏移量。

用BFS思想解题：
对地图上每个未访问过的表示陆地的点【表示一个岛屿】进行bfs，记录沉没的岛屿数；
在bfs中，每访问一个表示陆地的点就将其标记未已经访问，对该点上下左右四个方向查找陆地，将该岛屿整块进行标记，避免后续遍历时重复访问岛屿，在四个方向上查找陆地过程中记录当前点是否四个方向都是陆地，如果是，说明该岛屿不会完全沉没，返回0，如果遍历完整个岛屿都不存在这样的点，说明当前岛屿会完全沉没，返回1【完全沉没岛屿数+1】。

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;
public class Main {
    static boolean[][] visited = new boolean[1010][1010];
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static char[][] map = new char[1010][1010];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        String temp;
        for(int i=0;i<n;i++) {
            temp = sc.nextLine();
            map[i] = temp.toCharArray();
        }
        int res = 0; // 记录结果【沉没岛屿数】
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                if(map[i][j]=='#'&&!visited[i][j]) { // 当前点为陆地且未被访问
                    visited[i][j] = true; // 将其标记为已访问
                    res+=dfs(i,j); //记录结果
                }
            }
        }
        System.out.println(res);
    }
    // x,y表示当前要访问点的下标
    public static int dfs(int x,int y) {
        Queue<int[]> queue = new ArrayDeque<>(); // 用来装当前岛屿的点，进行逐个访问
        int flag = 1; //标记该岛屿是否会被完全淹没【是否存在四周都是陆地的陆地】，默认会被完全淹没
         // wx,wy保存队列中弹出点的坐标；
         //tx,ty保存该点在四个方向偏移的坐标；
         //k用来记录该点四面中是陆地的数量
        int k = 0,tx ,ty ,wx,wy;  
        int[] temp = null; // 保存队列中的弹出结点
        queue.offer(new int[]{x,y}); // 先将当前要访问的结点入队
        // 遍历访问包含该点的整个岛屿【避免后续重复遍历】
        while(!queue.isEmpty()) {
            temp = queue.poll();
            wx = temp[0];wy = temp[1];
            k = 0;
            // 看上下左右是否存在陆地
            for(int i=0;i<4;i++) {
                tx =wx+dx[i];
                ty =wy+dy[i];
                if(map[tx][ty]=='#') {
                    k++; 
                    if(!visited[tx][ty]) { // 如果该点未访问
                        visited[tx][ty] = true;  
                        queue.offer(new int[] {tx,ty}); // 入队
                    }
                }
            }
            if(k==4) flag = 0; //说明至少存在四面都是陆地的点，该岛屿不会被完全淹没
        }
        return flag;
    }
}