Day52--图论--101. 孤岛的总面积（卡码网），102. 沉没孤岛（卡码网），103. 水流问题（卡码网），104. 建造最大岛屿（卡码网）

Day52–图论–101. 孤岛的总面积（卡码网），102. 沉没孤岛（卡码网），103. 水流问题（卡码网），104. 建造最大岛屿（卡码网）

今天的题目都很有意思，全部都是岛，用深搜全部题都能做出来。其中《建造最大岛屿》需要思考很多细节问题，《水流问题》需要换个角度思考。其余两题比较简单。

101. 孤岛的总面积（卡码网）

方法：深搜

思路：

dfs函数返回值设为布尔值，只要岛屿的任意节点接触到边框，向上返回false。

每座岛屿都是从主函数进入的，所以在主函数中进行判断与加和操作。岛屿的节点全部是true，才能视为孤岛，加入到总面积。

import java.util.*;

public class Main {

    private static final int[][] dir = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
    private static int count = 0;

    private static boolean dfs(int[][] grid, boolean[][] visited, int x, int y) {

        // 岛屿面积++
        count++;
        // 孤岛标志，布尔变量
        boolean isolate = true;
        // 如果该岛接触到边框了，孤岛标志为false
        if (x == 0 || x == grid.length - 1 || y == 0 || y == grid[0].length - 1) {
            isolate = false;
        }

        for (int i = 0; i < dir.length; i++) {
            int nextX = x + dir[i][0];
            int nextY = y + dir[i][1];

            if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {
                continue;
            }
            if (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {
                visited[nextX][nextY] = true;
                boolean nextFlag = dfs(grid, visited, nextX, nextY);
                // 如果深搜的过程中，本岛的任何节点接触到边框，本岛都不再是孤岛
                // 进行与操作,只有每个节点都true,才能是孤岛
                isolate = isolate && nextFlag;
            }
        }
        return isolate;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[][] grid = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = in.nextInt();
            }
        }

        boolean[][] visited = new boolean[n][m];
        int totalArea = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    visited[i][j] = true;
                    // 因为是全局变量，所以每遇到一座岛，count归零
                    count = 0;
                    boolean isolate = dfs(grid, visited, i, j);
                    // 确定是孤岛，再加入到总面积
                    if (isolate) {
                        totalArea += count;
                    }
                }
            }
        }
        System.out.println(totalArea);
    }
}

102. 沉没孤岛（卡码网）

方法：深搜

思路：

第一步找到孤岛。

第二步，从同一个入口进去，再深搜一遍，因为是孤岛，所以四周要么就是visited为true，要么就是水，所以把能深搜到的visited为true的节点全部沉没。

import java.util.*;

public class Main {

    private static final int[][] dir = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

    // 判断孤岛
    private static boolean dfs(int[][] grid, boolean[][] visited, int x, int y) {

        // 孤岛标志，布尔变量
        boolean isolate = true;
        // 如果该岛接触到边框了，孤岛标志为false
        if (x == 0 || x == grid.length - 1 || y == 0 || y == grid[0].length - 1) {
            isolate = false;
        }

        for (int i = 0; i < dir.length; i++) {
            int nextX = x + dir[i][0];
            int nextY = y + dir[i][1];

            if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {
                continue;
            }
            if (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {
                visited[nextX][nextY] = true;
                boolean nextFlag = dfs(grid, visited, nextX, nextY);
                // 如果深搜的过程中，本岛的任何节点接触到边框，本岛都不再是孤岛
                // 进行与操作,只有每个节点都true,才能是孤岛
                isolate = isolate && nextFlag;
            }
        }
        return isolate;
    }

    // 沉没孤岛
    private static void dfsDown(int[][] grid, boolean[][] visited, int x, int y) {

        grid[x][y] = 0;

        for (int i = 0; i < dir.length; i++) {
            int nextX = x + dir[i][0];
            int nextY = y + dir[i][1];

            if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {
                continue;
            }
            // 注意这里不再是!visited了
            // 因为是孤岛，所以四周要么就是visited为true，要么就是水，所以不怕越界，大胆沉没
            if (visited[nextX][nextY] && grid[nextX][nextY] == 1) {
                dfsDown(grid, visited, nextX, nextY);
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[][] grid = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = in.nextInt();
            }
        }

        boolean[][] visited = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    visited[i][j] = true;
                    boolean isolate = dfs(grid, visited, i, j);
                    // 确定是孤岛，将孤岛沉没
                    if (isolate) {
                        dfsDown(grid, visited, i, j);
                    }
                }
            }
        }
        print(grid);
    }

    private static void print(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                System.out.print(grid[i][j] + " ");
            }
            System.out.println();
        }
    }
}

103. 水流问题（卡码网）

方法：深搜

思路：

如果顺序执行，那么每个节点O(mn)都要进行深搜O(mn)，就是O(n⁴)的时间复杂度。

所以反过来想问题。从边界出发，能够走到的最高点是哪里？

标记从左边，上边出发的点，能够遍历到的最大高度。

标记从右边，下边出发的店，能够遍历到的最大高度。

二者都标记过的，就是说明，该高度的水，可以同时流到两组的边界。

import java.util.*;

public class Main {
    // 方向标
    private static final int[][] dir = { { 0, 1 }, { 0, -1 }, { -1, 0 }, { 1, 0 } };

    // 深搜
    static void dfs(int[][] grid, boolean[][] visited, int x, int y) {
        // 递归终止条件
        // 这次写在进入dfs之后，而不是dfs之前，是因为要进dfs的地方太多了，写在这里就一次
        if (visited[x][y]) {
            return;
        }
        visited[x][y] = true;

        for (int i = 0; i < 4; i++) {
            int nextX = x + dir[i][0];
            int nextY = y + dir[i][1];
            if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {
                continue;
            }
            // 注意：这里是从低向高遍历
            if (!visited[nextX][nextY] && grid[x][y] <= grid[nextX][nextY]) {
                dfs(grid, visited, nextX, nextY);
            }
        }
    }

    // 主函数
    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();
            }
        }

        // 标记从第一组边界上的节点出发，可以遍历的节点
        boolean[][] firstBorder = new boolean[n][m];
        // 标记从第二组边界上的节点出发，可以遍历的节点
        boolean[][] secondBorder = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            // 左边界出发，向高处遍历
            dfs(grid, firstBorder, i, 0);
            // 右边界出发
            dfs(grid, secondBorder, i, m - 1);
        }

        for (int j = 0; j < m; j++) {
            // 上边界出发
            dfs(grid, firstBorder, 0, j);
            // 下边界出发
            dfs(grid, secondBorder, n - 1, j);
        }

        // 打印输出
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 如果这个节点，从第一组边界和第二组边界出发都遍历过，就是结果
                if (firstBorder[i][j] && secondBorder[i][j]) {
                    System.out.println(i + " " + j);
                }
            }
        }
    }
}

104. 建造最大岛屿（卡码网）

这道题，理解起来不难，但是要做的时候步骤很多，而且很多细节的问题需要把控到。

最关键的地方：每完成一个步骤，把对应的矩阵打印出来看，看看是否达到自己的设定。

方法：深搜

思路：

1. 第一次深搜：给岛屿编号，并找到该岛屿的总面积
   • 深搜后，grid矩阵，记录岛屿的编号
   • 岛屿的总面积为count
   • 每一个遍历过的节点，把对应的area矩阵的位置，设为-1，待会要用
2. 第二次深搜：在刚才的节点再进去深搜一遍，在area矩阵，每个节点都记录整个岛屿的面积
   • 深搜的时候，因为visited数组已经被用过了，要再想深搜退出的条件，不能再是!visited了——每进一层深搜，变化的是什么呢？area值。所以当area值是-1的节点，就进去，area为0或者已经有值的节点，不进去。
   • 深搜后，area矩阵，每个节点都记录整个岛屿的面积
3. 遍历每个水节点，假设当前水节点变为陆地之后，总面积为temp
   • 检查水节点的上下左右节点。
   • 每个节点，都要先检查编号，是否是同一个岛屿（使用set），如果不是同一个岛屿，area面积加入到temp中
4. 最后，检查maxArea是否为0。如果仍是0，证明给出的矩阵，全是陆地，没有任何水，返回陆地的面积n*m

import java.util.*;

public class Main {

    // 方向标
    private static final int[][] dir = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
    // 面积计数器
    private static int count = 0;
    // 岛屿编号
    private static int islandNumber = 0;

    // 深搜，找到岛屿并编号
    private static void dfs(int[][] grid, boolean[][] visited, int[][] area, int x, int y) {
        // 岛屿面积+1
        count++;
        // 岛屿编号设定
        grid[x][y] = islandNumber;
        // 设定面积的时候要用的判定条件；第一次深搜的时候，将节点面积设为-1
        area[x][y] = -1;

        // 常规的深搜
        for (int i = 0; i < dir.length; i++) {
            int nextX = x + dir[i][0];
            int nextY = y + dir[i][1];
            if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {
                continue;
            }
            if (!visited[nextX][nextY] && grid[nextX][nextY] != 0) {
                visited[nextX][nextY] = true;
                dfs(grid, visited, area, nextX, nextY);
            }
        }
    }

    // 深搜，设置岛屿面积
    private static void setArea(int[][] grid, boolean[][] visited, int[][] area, int x, int y) {
        // 设定岛屿面积
        area[x][y] = count;

        // 常规的深搜
        for (int i = 0; i < dir.length; i++) {
            int nextX = x + dir[i][0];
            int nextY = y + dir[i][1];

            if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {
                continue;
            }
            // 在第一次深搜的时候，岛屿每个节点的面积为-1
            // 这是第二次深搜，每设定一个节点，该节点的面积就不可能是-1
            // area从-1变成count。这里起到一个visited=true的标记作用。
            if (area[nextX][nextY] < 0 && grid[nextX][nextY] != 0) {
                setArea(grid, visited, area, nextX, nextY);
            }
        }
    }

    // 主函数
    public static void main(String[] args) {
        // 录入题目数据
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[][] grid = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = in.nextInt();
            }
        }

        // 标记数组,第一遍深搜用
        boolean[][] visited = new boolean[n][m];
        // 面积数组,记录每个节点所在岛屿的面积
        int[][] area = new int[n][m];

        // 第一第二次深搜,找到岛屿,标记岛屿编号,设定岛屿面积
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 因为设定标号的时候,直接在grid上操作了,所以这里不能再用grid[i][j] == 1
                if (!visited[i][j] && grid[i][j] != 0) {
                    // 每到这里,都是一个新的岛屿,所以count=0
                    count = 0;
                    // 岛屿编号+1
                    islandNumber++;
                    // 第一次深搜
                    visited[i][j] = true;
                    dfs(grid, visited, area, i, j);
                    // 第二次深搜:设定岛屿面积
                    setArea(grid, visited, area, i, j);
                }
            }
        }

        // 遍历每个水,开始将某个水节点设为变为陆地
        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 遍历水
                if (grid[i][j] == 0) {
                    // 要用set记录陆地的编号
                    Set<Integer> set = new HashSet<>();
                    // 本节点(水)的面积为1
                    int temp = 1;
                    // 水的四周节点
                    // 上
                    if (i > 0) {
                        // 把编号加到set中
                        set.add(grid[i - 1][j]);
                        temp += area[i - 1][j];
                    }
                    // 左
                    if (j > 0) {
                        // 检查与上是否是同一个岛屿编号
                        if (!set.contains(grid[i][j - 1])) {
                            temp += area[i][j - 1];
                            // 把编号加到set中
                            set.add(grid[i][j - 1]);
                        }
                    }
                    // 下
                    if (i < grid.length - 1) {
                        if (!set.contains(grid[i + 1][j])) {
                            temp += area[i + 1][j];
                            set.add(grid[i + 1][j]);
                        }
                    }
                    // 右
                    if (j < grid[0].length - 1) {
                        if (!set.contains(grid[i][j + 1])) {
                            temp += area[i][j + 1];
                        }
                    }
                    // 刷新最大面积
                    maxArea = Math.max(maxArea, temp);
                }
            }
        }
        // 最后,要判断maxArea是否为0,如果仍是0,证明给出的矩阵,全是陆地,没有任何水,返回陆地的面积
        System.out.println(maxArea == 0 ? n * m : maxArea);
        // print(area);
    }

    // 打印grid或者area来检查
    private static void print(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                System.out.print(grid[i][j] + " ");
            }
            System.out.println();
        }
    }
}

这道题踩了很多坑。第一次提交的时候，矩阵全是陆地，返回面积错误；第二次提交的时候，没有用编号和set区分岛屿，水的四周其实是同一座岛屿，返回面积错误。