第十一章：图论part03

101. 孤岛的总面积

基础题目 可以自己尝试做一做 。
文章讲解

思路

• 注意孤岛的定义是单元格不接触边缘。
• 本题要求找到不靠边的陆地面积，那么我们只要从周边找到陆地然后 通过 dfs或者bfs 将周边靠陆地且相邻的陆地都变成海洋，然后再去重新遍历地图 统计此时还剩下的陆地就可以了。

DFS

import java.util.*;

public class Main{
    static int count;
    static int[][] dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; //下左上右
    
    public static void dfs(int[][] grid, int x, int y){
        grid[x][y] = 0; // 将当前格子标记为已访问  这里不需要单独的visited数组
        count++; // 增加岛屿面积计数
        
        // 向四个方向遍历
        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;
            
            // 如果下一个坐标是陆地，继续 DFS
            if(grid[nextx][nexty] == 1) dfs(grid, nextx, nexty);
        }
        
    }
    
    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++){
            if(grid[i][0] == 1) dfs(grid, i, 0);
            if(grid[i][m - 1] == 1) dfs(grid, i, m - 1);
            
        }
        
        // 处理上下边界，所以行是固定的
        for(int j = 0; j < m; j++){
            if(grid[0][j] == 1) dfs(grid, 0, j);
            if(grid[n - 1][j] == 1) dfs(grid, n - 1, j);
        }
        
        // 重置计数器
        count = 0;
        
        // 遍历整个网格，统计所有符合条件的陆地空格数量
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(grid[i][j] == 1) dfs(grid, i, j);
            }
        }
        System.out.println(count);
    }
}

BFS

import java.util.*;

public class Main{
    static int count;
    static int[][] dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; //下左上右
    
    public static void bfs(int[][] grid, int x, int y){
        // 初始化
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        grid[x][y] = 0; // 标记初始坐标已访问
        count++;
        
        // 当队列不为空时，持续处理
        while(!queue.isEmpty()){
            int[] current = queue.poll();// 获取并移除队列头部的元素
            int curx = current[0];// 当前处理的 x 坐标
            int cury = current[1];// 当前处理的 y 坐标
            
            // 遍历四个方向
            for(int i = 0; i < 4; i++){
                int nextx = curx + dir[i][0];
                int nexty = cury + dir[i][1];
                
                // 检查下一个坐标是否越界
                if(nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue;
                if(grid[nextx][nexty] == 1){
                    queue.offer(new int[]{nextx,nexty});
                    count++;
                    grid[nextx][nexty] = 0; // 标记为已访问
                }
            }
        }
        
        
    }
    
    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++){
            if(grid[i][0] == 1) bfs(grid, i, 0);
            if(grid[i][m - 1] == 1) bfs(grid, i, m - 1);
            
        }
        
        // 处理上下边界，所以行是固定的
        for(int j = 0; j < m; j++){
            if(grid[0][j] == 1) bfs(grid, 0, j);
            if(grid[n - 1][j] == 1) bfs(grid, n - 1, j);
        }
        
        // 重置计数器
        count = 0;
        
        // 遍历整个网格，统计所有符合条件的陆地空格数量
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(grid[i][j] == 1) bfs(grid, i, j);
            }
        }
        System.out.println(count);
    }
}

102. 沉没孤岛

和上一题差不多，尝试自己做做
文章讲解

思路

• 依然是从地图周边出发，将周边空格相邻的陆地都做上标记，然后在遍历一遍地图，遇到 陆地 且没做过标记的，那么都是地图中间的 陆地 ，全部改成水域就行。
  步骤一：深搜或者广搜将地图周边的 1 （陆地）全部改成 2 （特殊标记）
  步骤二：将水域中间 1 （陆地）全部改成 水域（0）
  步骤三：将之前标记的 2 改为 1 （陆地）

import java.util.*;

public class Main{
    static int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};
    
    public static void dfs(int[][] grid, int x, int y){
        grid[x][y] = 2;// 标记当前格子为已访问
        
        // 向四个方向遍历
        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(grid[nextx][nexty] == 0 || grid[nextx][nexty] == 2) continue;
            
            dfs(grid, nextx, nexty);
        }
        
    }
    
    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++){
            if(grid[i][0] == 1) dfs(grid, i, 0);
            if(grid[i][m - 1] == 1) dfs(grid, i,  m - 1);
        }
        
        // 处理上下侧边
        for(int j = 0; j < m; j++){
            if(grid[0][j] == 1) dfs(grid, 0, j);
            if(grid[n - 1][j] == 1) dfs(grid, n - 1, j);
        }
        
        // 步骤二和步骤三
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(grid[i][j] == 1) grid[i][j] = 0;
                if(grid[i][j] == 2) grid[i][j] = 1;
            }
        }
        
        // 输出结果
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                System.out.print(grid[i][j] + " ");
            }
            System.out.println();
        } 
    }
}

103. 水流问题

需要点优化思路，建议先自己读题，想出一个解题方法，有时间就自己写代码，没时间就直接看题解，优化方式 会让你 耳目一新。
文章讲解

思路

从第一组边界上的节点 逆流而上，将遍历过的节点都标记上。

image.png

同样从第二组边界的边上节点 逆流而上，将遍历过的节点也标记上。

image.png

然后两方都标记过的节点就是既可以流太平洋也可以流大西洋的节点。

import java.util.Scanner;
import java.util.Arrays;

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

    // 深度优先搜索 (DFS) 方法
    public static void dfs(int[][] grid, boolean[][] visited, int x, int y) {
        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 >= n || nexty < 0 || nexty >= m) continue;
            // 从低向高遍历
            if (grid[x][y] > grid[nextx][nexty]) continue;

            dfs(grid, visited, nextx, nexty); // 递归调用 DFS
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        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();
            }
        }

        // 标记从第一组边界上的节点出发，可以遍历的节点
        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);
                }
            }
        }
    }
}

本题整体的时间复杂度其实是： 2 * n * m + n * m ，所以最终时间复杂度为 O(n * m) 。空间复杂度为：O(n * m) 这个就不难理解了。开了几个 n * m 的数组。
时间复杂度怎么算的暂时没整明白，二刷记得看。

104.建造最大岛屿

同样优化思路也会让你耳目一新，自己想比较难想出来。
文章讲解

思路

暴力解法：

应该是遍历地图尝试 将每一个 0 改成1，然后去搜索地图中的最大的岛屿面积。
计算地图的最大面积：遍历地图 + 深搜岛屿，时间复杂度为 n * n。
每改变一个0的方格，都需要重新计算一个地图的最大面积，所以 整体时间复杂度为：n^4。

优化思路：

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

• 第一步：一次遍历地图，得出各个岛屿的面积，并做编号记录。可以使用map记录，key为岛屿编号，value为岛屿面积

• 第二步：再遍历地图，遍历0的方格（因为要将0变成1），并统计该1（由0变成的1）周边岛屿面积，将其相邻面积相加在一起，遍历所有 0 之后，就可以得出 选一个0变成1 之后的最大面积。

image.png

image.png

代码如下

    static int count;
    static int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 四个方向

    public void dfs(int[][] grid, boolean[][] visited, int x, int y, int mark) {
        if (visited[x][y] || grid[x][y] == 0) return; // 终止条件：访问过的节点 或者 遇到海水
        visited[x][y] = true; // 标记访问过
        grid[x][y] = mark; // 给陆地标记新标签
        count++;
        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;  // 越界了，直接跳过
            dfs(grid, visited, nextx, nexty, mark);
        }
    }

    public int largestIsland(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        boolean[][] visited = new boolean[n][m]; // 标记访问过的点
        Map<Integer, Integer> gridNum = new HashMap<>();
        int mark = 2; // 记录每个岛屿的编号
        boolean isAllGrid = true; // 标记是否整个地图都是陆地

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 0) isAllGrid = false;
                if (!visited[i][j] && grid[i][j] == 1) {
                    count = 0;
                    dfs(grid, visited, i, j, mark); // 将与其链接的陆地都标记上
                    gridNum.put(mark, count); // 记录每一个岛屿的面积
                    mark++; // 记录下一个岛屿编号
                }
            }
        }

        if (isAllGrid) return n * m; // 如果整个地图都是陆地，返回总面积

        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 0) {
                    Set<Integer> seen = new HashSet<>();
                    int area = 1; // 将这个0变为1后的新面积
                    for (int k = 0; k < 4; k++) {
                        int nextx = i + dir[k][0];
                        int nexty = j + dir[k][1];
                        if (nextx >= 0 && nextx < n && nexty >= 0 && nexty < m && grid[nextx][nexty] > 1) {
                            int id = grid[nextx][nexty];
                            if (!seen.contains(id)) {
                                area += gridNum.get(id);
                                seen.add(id);
                            }
                        }
                    }
                    maxArea = Math.max(maxArea, area);
                }
            }
        }
        return maxArea;
    }

image.png

也就是遍历每一个0的方格，并统计其相邻岛屿面积，最后取一个最大值。

这个过程的时间复杂度也为 n * n。

所以整个解法的时间复杂度，为 n * n + n * n 也就是 n^2。

当然这里还有一个优化的点，就是 可以不用 visited数组，因为有mark来标记，所以遍历过的grid[i][j]是不等于1的。

代码如下：

import java.util.*;

public class Solution {
    static int count;
    static int n, m;
    static int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 四个方向

    public static void dfs(int[][] grid, int x, int y, int mark) {
        if (grid[x][y] != 1 || grid[x][y] == 0) return; // 终止条件：访问过的节点 或者 遇到海水
        grid[x][y] = mark; // 给陆地标记新标签
        count++;
        for (int i = 0; i < 4; i++) {
            int nextx = x + dir[i][0];
            int nexty = y + dir[i][1];
            if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;  // 越界了，直接跳过
            dfs(grid, nextx, nexty, mark);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        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();
            }
        }

        Map<Integer, Integer> gridNum = new HashMap<>();
        int mark = 2; // 记录每个岛屿的编号
        boolean isAllGrid = true; // 标记是否整个地图都是陆地

        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) {
                    count = 0;
                    dfs(grid, i, j, mark); // 将与其链接的陆地都标记上
                    gridNum.put(mark, count); // 记录每一个岛屿的面积
                    mark++; // 记录下一个岛屿编号
                }
            }
        }
    }
}

整体代码如下：

import java.util.*;

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

    public static void dfs(int[][] grid, boolean[][] visited, int x, int y, int mark) {
        if (visited[x][y] || grid[x][y] == 0) return; // 终止条件：访问过的节点 或者 遇到海水
        visited[x][y] = true; // 标记访问过
        grid[x][y] = mark; // 给陆地标记新标签
        count++;
        for (int i = 0; i < 4; i++) {
            int nextx = x + dir[i][0];
            int nexty = y + dir[i][1];
            if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;  // 越界了，直接跳过
            dfs(grid, visited, nextx, nexty, mark);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        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();
            }
        }

        boolean[][] visited = new boolean[n][m]; // 标记访问过的点
        Map<Integer, Integer> gridNum = new HashMap<>();
        int mark = 2; // 记录每个岛屿的编号
        boolean isAllGrid = true; // 标记是否整个地图都是陆地

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 0) isAllGrid = false;
                if (!visited[i][j] && grid[i][j] == 1) {
                    count = 0;
                    dfs(grid, visited, i, j, mark); // 将与其链接的陆地都标记上
                    gridNum.put(mark, count); // 记录每一个岛屿的面积
                    mark++; // 记录下一个岛屿编号
                }
            }
        }

        if (isAllGrid) {
            System.out.println(n * m); // 如果都是陆地，返回全面积
            return; // 结束程序
        }

        // 以下逻辑是根据添加陆地的位置，计算周边岛屿面积之和
        int result = 0; // 记录最后结果
        Set<Integer> visitedGrid = new HashSet<>(); // 标记访问过的岛屿
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                count = 1; // 记录连接之后的岛屿数量
                visitedGrid.clear(); // 每次使用时，清空
                if (grid[i][j] == 0) {
                    for (int k = 0; k < 4; k++) {
                        int neari = i + dir[k][1]; // 计算相邻坐标
                        int nearj = j + dir[k][0];
                        if (neari < 0 || neari >= n || nearj < 0 || nearj >= m) continue;
                        if (visitedGrid.contains(grid[neari][nearj])) continue; // 添加过的岛屿不要重复添加
                        // 把相邻四面的岛屿数量加起来
                        count += gridNum.getOrDefault(grid[neari][nearj], 0);
                        visitedGrid.add(grid[neari][nearj]); // 标记该岛屿已经添加过
                    }
                }
                result = Math.max(result, count);
            }
        }
        System.out.println(result);
    }
}