代码随想录算法训练营第五十五天|101.孤岛的总面积、102.沉没孤岛、103.水流问题、104.建造最大岛屿

101.孤岛的总面积

题目链接：101.孤岛的总面积沉没孤岛
文档讲解：代码随想录
状态：不会

思路：
步骤1：将边界上的陆地变为海洋
步骤2：计算孤岛的总面积

题解：

public class Main {
    // 保存四个方向
    static int[][] dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 读取网格的行数和列数
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] grid = new int[n][m];
        // 读取网格数据
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = sc.nextInt();
            }
        }
        int sum = 0;
        // 将边界上的陆地变为海洋
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1 && (i == 0 || i == n - 1 || j == 0 || j == m - 1)) {
                    dfs(grid, i, j);
                }
            }
        }
        // 计算孤岛的总面积
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    sum += dfs(grid, i, j);
                }
            }
        }
        // 输出孤岛的总面积
        System.out.println(sum);
    }

    /**
     * 深度优先搜索遍历陆地，将其变为海洋，并计算陆地的面积
     * @param grid 网格
     * @param x 当前的行坐标
     * @param y 当前的列坐标
     * @return 陆地的面积
     */
    public static int dfs(int[][] grid, int x, int y) {
        // 如果超出网格边界或者当前位置是海洋，则返回0
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == 0) {
            return 0;
        }
        // 将当前位置的陆地变为海洋
        grid[x][y] = 0;
        int sum = 1;
        // 向四个方向遍历
        for (int i = 0; i < 4; i++) {
            int nextX = x + dir[i][0];
            int nextY = y + dir[i][1];
            sum += dfs(grid, nextX, nextY);
        }
        return sum;
    }
}

102.沉没孤岛

题目链接：102.沉没孤岛
文档讲解：代码随想录
状态：还行

思路：在上题的基础上额外标记下边界上的陆地

题解：

public class Main {
    // 保存四个方向
    static int[][] dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 读取网格的行数和列数
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] grid = new int[n][m];
        // 读取网格数据
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = sc.nextInt();
            }
        }
        // 标记边界上的陆地
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1 && (i == 0 || i == n - 1 || j == 0 || j == m - 1)) {
                    dfsEdge(grid, i, j);
                }
            }
        }

        // 沉没孤岛
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    dfs(grid, i, j);
                }
            }
        }

        // 恢复标记为-1的边界陆地为原始状态
        for (int[] ints : grid) {
            for (int k : ints) {
                if (k == -1) {
                    k = 1;
                }
                System.out.print(k + " ");
            }
            System.out.println();
        }
    }

    /**
     * 深度优先搜索标记边界上的陆地
     * @param grid 网格
     * @param x 当前的行坐标
     * @param y 当前的列坐标
     */
    public static void dfsEdge(int[][] grid, int x, int y) {
        // 如果超出网格边界或者当前位置不是陆地，则返回
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] != 1) {
            return;
        }
        // 将边界上的陆地标记为-1
        grid[x][y] = -1;
        // 向四个方向遍历
        for (int i = 0; i < 4; i++) {
            int nextX = x + dir[i][0];
            int nextY = y + dir[i][1];
            dfsEdge(grid, nextX, nextY);
        }
    }

    /**
     * 深度优先搜索沉没孤岛
     * @param grid 网格
     * @param x 当前的行坐标
     * @param y 当前的列坐标
     */
    public static void dfs(int[][] grid, int x, int y) {
        // 如果超出网格边界或者当前位置不是陆地，则返回
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] != 1) {
            return;
        }
        // 将当前位置的陆地沉没
        grid[x][y] = 0;
        // 向四个方向遍历
        for (int i = 0; i < 4; i++) {
            int nextX = x + dir[i][0];
            int nextY = y + dir[i][1];
            dfs(grid, nextX, nextY);
        }
    }
}

103.水流问题

题目链接：103.水流问题
文档讲解：代码随想录
状态：没做出来

思路：
雨水的流动方向是从高到低，每个单元格上的雨水只能流到高度小于等于当前单元格的相邻单元格。从一个单元格开始，通过搜索的方法模拟雨水的流动，则可以判断雨水是否可以从该单元格流向边界。

如果直接以每个单元格作为起点模拟雨水的流动，则会重复遍历每个单元格，导致时间复杂度过高。为了降低时间复杂度，可以从矩阵的边界开始反向搜索寻找雨水流向边界的单元格，反向搜索时，每次只能移动到高度相同或更大的单元格。

题解：

public class Main {
    // 方向数组，包括右、下、左、上四个方向
    static int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    /**
     * 找到能够流向两个边界的坐标
     * @param heights 给定的高度矩阵
     * @return 能够流向两个边界的坐标列表
     */
    public static List<int[]> WaterFlow(int[][] heights) {
        List<int[]> result = new ArrayList<>();
        if (heights == null || heights.length == 0 || heights[0].length == 0) {
            return result;
        }

        int m = heights.length;     // 矩阵的行数
        int n = heights[0].length;  // 矩阵的列数

        boolean[][] firstBoard = new boolean[m][n];  // 记录能流向第一个边界的坐标
        boolean[][] secondBoard = new boolean[m][n]; // 记录能流向第二个边界的坐标

        // 遍历第一列和第一行，找到能流向第一个边界的坐标
        for (int i = 0; i < m; i++) {
            dfs(heights, firstBoard, i, 0);
        }
        for (int j = 1; j < n; j++) {
            dfs(heights, firstBoard, 0, j);
        }

        // 遍历最后一列和最后一行，找到能流向第二个边界的坐标
        for (int i = 0; i < m; i++) {
            dfs(heights, secondBoard, i, n - 1);
        }
        for (int j = 0; j < n - 1; j++) {
            dfs(heights, secondBoard, m - 1, j);
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dfs(heights,firstBoard,i,j);
                dfs(heights,secondBoard,i,j);
            }
        }

        // 找到能流向两个边界的坐标
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (firstBoard[i][j] && secondBoard[i][j]) {
                    result.add(new int[]{i, j});
                }
            }
        }

        return result;
    }

    /**
     * 深度优先搜索DFS
     * @param heights 给定的高度矩阵
     * @param visited 记录访问过的坐标
     * @param x 当前点的行坐标
     * @param y 当前点的列坐标
     */
    private static void dfs(int[][] heights, boolean[][] visited, int x, int y) {
        visited[x][y] = true;   // 标记当前点已经访问过
        int m = heights.length; // 矩阵的行数
        int n = heights[0].length;  // 矩阵的列数

        // 遍历四个方向
        for (int[] dir : directions) {
            int newX = x + dir[0];   // 新点的行坐标
            int newY = y + dir[1];   // 新点的列坐标

            // 如果新点在矩阵范围内，并且新点的高度不小于当前点的高度，且新点未被访问过，则继续递归
            if (newX >= 0 && newX < m && newY >= 0 && newY < n && !visited[newX][newY] && heights[newX][newY] >= heights[x][y]) {
                dfs(heights, visited, newX, newY);
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 矩阵的行数
        int m = scanner.nextInt(); // 矩阵的列数
        int[][] grid = new int[n][m]; // 创建高度矩阵
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = scanner.nextInt(); // 输入矩阵元素
            }
        }

        // 调用函数找到能够流第一边界和第二边界的点
        List<int[]> result = WaterFlow(grid);

        // 输出结果
        for (int[] point : result) {
            System.out.println(point[0] + " " + point[1]);
        }
    }
}

104.建造最大岛屿

题目链接：104.建造最大岛屿
文档讲解：代码随想录
状态：只想到暴力

思路：
暴力的思想：本题的一个暴力想法，应该是遍历地图尝试 将每一个 0 改成1，然后去搜索地图中的最大的岛屿面积。

其实每次深搜遍历计算最大岛屿面积，我们都做了很多重复的工作。

只要用一次深搜把每个岛屿的面积记录下来就好。

第一步：一次遍历地图，得出各个岛屿的面积的同时做编号记录。可以使用map记录，key为岛屿编号，value为岛屿面积。（遍历过后的陆地标记为编号数字，map中通过编号数字对应岛屿面积）

第二步：再遍历地图，遍历0的方格（因为要将0变成1），并统计该1（由0变成的1）周边岛屿面积，将其相邻面积相加在一起，遍历所有 0 之后，就可以得出 选一个0变成1 之后的最大面积。对每个0方格遍历时要考虑相邻坐标越界，相邻格子的岛屿是否已经计算过，最后才是累加相邻岛屿的面积，更新最大岛屿面积。

题解：

public class Main {
    // 定义四个方向的移动
    static int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

    // 深度优先搜索函数，用于标记岛屿并计算其面积
    public static int dfs(int[][] grid, int x, int y, int mark) {
        int n = grid.length;
        int m = grid[0].length;
        // 如果坐标越界或当前格子不是陆地（不是1），则返回0
        if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] != 1) {
            return 0;
        }
        // 将当前陆地格子标记为当前岛屿的标记
        grid[x][y] = mark;
        int sum = 1; // 记录当前岛屿的面积
        // 遍历四个方向，继续深度优先搜索
        for (int i = 0; i < 4; i++) {
            int newX = x + dir[i][0];
            int newY = y + dir[i][1];
            sum += dfs(grid, newX, newY, mark); // 累加相邻陆地的面积
        }
        return sum;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 输入网格的行数
        int m = scanner.nextInt(); // 输入网格的列数
        int[][] grid = new int[n][m]; // 初始化网格
        // 读取网格数据
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }

        HashMap<Integer, Integer> map = new HashMap<>(); // 存储每个岛屿的标记及其面积
        boolean isAllGrid = true; // 标记是否整个地图都是陆地

        int mark = 2; // 从2开始标记岛屿，因为1已经表示陆地
        // 遍历网格，对每个未标记的陆地进行DFS
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 0) {
                    isAllGrid = false; // 如果有海洋格子，标记不是全陆地
                }
                if (grid[i][j] == 1) {
                    int area = dfs(grid, i, j, mark); // 对新的岛屿进行DFS并计算面积
                    map.put(mark++, area); // 记录岛屿的标记和面积
                }
            }
        }

        // 如果整个地图都是陆地，直接返回面积
        if (isAllGrid) {
            System.out.println(n * m);
            return;
        }

        int maxArea = 0; // 记录最大岛屿面积
        // 遍历网格，尝试将每个海洋格子变为陆地，计算可能的最大岛屿面积
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 0) {
                    int sum = 1; // 初始面积为1，因为将海洋格子变为陆地
                    // 在计算相邻岛屿面积时，需要避免重复计算，因此使用一个哈希集合 (visitedMarks) 来记录已经计算过的岛屿编号。
                    HashSet<Integer> visitedMarks = new HashSet<>(); // 存储已经访问过的岛屿标记

                    // 遍历四个方向，计算相邻岛屿的总面积
                    for (int k = 0; k < 4; k++) {
                        int newX = i + dir[k][0];
                        int newY = j + dir[k][1];
                        // 如果相邻坐标越界，跳过
                        if (newX < 0 || newX >= n || newY < 0 || newY >= m) continue;
                        int markValue = grid[newX][newY];
                        // 如果相邻格子的岛屿已经计算过，跳过
                        if (visitedMarks.contains(markValue)) continue;
                        Integer s = map.get(markValue); // 获取相邻岛屿的面积
                        if (s != null) {
                            sum += s; // 累加相邻岛屿的面积
                            visitedMarks.add(markValue); // 标记该岛屿已经访问
                        }
                    }
                    maxArea = Math.max(maxArea, sum); // 更新最大岛屿面积
                }
            }
        }
        System.out.println(maxArea); // 输出最大岛屿面积
    }
}