代码随想录Day52：图论（孤岛的总面积、沉没孤岛、水流问题、建造最大岛屿）
一、实战
101孤岛的总面积
101. 孤岛的总面积
孤岛是指不靠边的陆地面积，如图
思路：那么只要从周边找到陆地然后 通过 dfs或者bfs 将周边靠陆地且相邻的陆地都变成海洋，然后再去重新遍历地图 统计此时还剩下的陆地就可以了。效果如下
这里的代码是广搜无终止条件版本，本题代码无需visited数组，因为我们在遍历周边的时候直接把grid数组中的不符合要求的陆地（1）变成海洋（0），已经起到了类似的作用，所以可以不用再设置一个visited数组。
package org.example;//具体运行时去掉import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt(); // 读取网格行数int m = scan.nextInt(); // 读取网格列数int[][] grid = new int[n][m];// 输入网格数据for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {grid[i][j] = scan.nextInt();}}// 从最左列和最右列的陆地开始，向内DFS淹没与边界相连的陆地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); // 右边界}// 从最上行和最下行的陆地开始，向内DFS淹没与边界相连的陆地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); // 下边界}// 统计剩余的陆地数量（即不与边界相连的“封闭岛屿”或“飞地”）int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1) result++; // 剩下的1就是被水包围的陆地}}System.out.println(result); // 输出答案scan.close();}// 四个方向：右、下、上、左private static final int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};/*** DFS：从边界上的陆地出发，将所有相连的陆地“淹没”为水（标记为0）* 目的：去除与边界相连的陆地（这些不属于“封闭岛屿”）*/private static void dfs(int[][] grid, int i, int j) {grid[i][j] = 0; // 将当前陆地变为水（淹没）// 向四个方向扩展for (int k = 0; k < 4; k++) {int nextx = i + dir[k][0];int nexty = j + dir[k][1];// 越界检查if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length)continue;// 只对仍是陆地的位置继续DFSif (grid[nextx][nexty] == 1) {dfs(grid, nextx, nexty);}}}
}力扣中类似题目：1254. 统计封闭岛屿的数目 - 力扣（LeetCode）
102沉没孤岛
102. 沉没孤岛
这道题目和0101.孤岛的总面积 (opens new window)正好反过来了，上一题是求地图中间的空格数，而本题是要把地图中间的 1 都改成 0 。思路可以完全一样，从地图周边出发，将周边空格相邻的陆地都做上标记，然后在遍历一遍地图，遇到 陆地 且没做过标记的，那么都是地图中间的 陆地 ，全部改成水域就行。不用额外定义空间，标记周边的陆地，可以直接改陆地为其他特殊值作为标记。
步骤一：深搜或者广搜将地图周边的 1 （陆地）全部改成 2 （特殊标记）
步骤二：将水域中间 1 （陆地）全部改成 水域（0）
步骤三：将之前标记的 2 改为 1 （陆地）
注意步骤二三可以同时进行
代码是深搜无终止条件版本：
package org.example;//具体运行时去掉import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt(); // 读取网格行数int m = scan.nextInt(); // 读取网格列数int[][] grid = new int[n][m];// 输入网格数据（0:水, 1:陆地）for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {grid[i][j] = scan.nextInt();}}// 从左、右边界出发，标记所有与边界相连的陆地（标记为2）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); // 右边界}// 从上、下边界出发，标记所有与边界相连的陆地（标记为2）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] == 2) {grid[i][j] = 1; // 标记为2的：原是与边界相连的陆地 → 恢复为1（保留）}else if (grid[i][j] == 1) {grid[i][j] = 0; // 剩下的1：孤立陆地 → 淹没为0}System.out.print(grid[i][j] + " ");}System.out.println();}}// 四个方向：右、下、左、上private static final int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};/*** DFS：从边界陆地出发，将所有相连的陆地标记为2（临时标记）* 目的：区分“与边界相连的陆地”和“被水包围的孤立陆地”*/private static void dfs(int[][] grid, int i, int j) {grid[i][j] = 2; // 标记当前陆地为已访问（2表示与边界相连）// 向四个方向扩展for (int k = 0; k < 4; k++) {int nextx = i + dir[k][0];int nexty = j + dir[k][1];// 越界检查if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length)continue;// 只对原始陆地（1）进行递归标记if (grid[nextx][nexty] == 1) {dfs(grid, nextx, nexty);}}}
}103水流问题
103. 水流问题
暴力解法：遍历每个点，然后通过dfs或者bfs看这个点能不能同时到达第一组边界和第二组边界。但是整体时间复杂度是 O(m^2 * n^2) ，会超时。
优化解法：反过来想，从第一组边界上的节点 逆流而上，将遍历过的节点都标记上。同样从第二组边界的边上节点 逆流而上，将遍历过的节点也标记上。两方都标记过的节点就是既可以流向第一组边界也可以流向第二组边界的节点。
两个方向交界的这些节点就是我们最后要求的节点。
代码是dfs无终止条件版本：
package org.example;//具体运行时去掉import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt(); // 读取网格行数int m = scan.nextInt(); // 读取网格列数int[][] grid = new int[n][m];// 输入网格高度数据for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {grid[i][j] = scan.nextInt();}}// 标记能流向“左/上边界”（太平洋）的单元格boolean[][] firstborder = new boolean[n][m];// 标记能流向“右/下边界”（大西洋）的单元格boolean[][] secondborder = new boolean[n][m];// 从左右边界出发，DFS 标记可到达的区域for (int i = 0; i < n; i++) {dfs(grid, firstborder, i, 0); // 从最左列（太平洋）开始dfs(grid, secondborder, i, m - 1); // 从最右列（大西洋）开始}// 从上下边界出发，DFS 标记可到达的区域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); // 满足双边界可达}}}}// 四个方向：右、下、左、上private static final int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};/*** DFS：从边界向内搜索，标记所有可通过非递减路径到达当前边界的点* 实际含义：水可以从这些点沿非递增路径流到对应海洋*/private static void dfs(int[][] grid, boolean[][] border, int x, int y) {if (border[x][y]) return; // 已访问过，跳过border[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 (grid[nextx][nexty] >= grid[x][y]) {dfs(grid, border, nextx, nexty);}}}
}104建造最大岛屿
104. 建造最大岛屿
暴力思路：遍历地图尝试 将每一个 0 改成1，然后去搜索地图中的最大的岛屿面积。，计算地图的最大面积：遍历地图 + 深搜岛屿，时间复杂度为 n * n。每改变一个0的方格，都需要重新计算一个地图的最大面积，所以 整体时间复杂度为：n^4，复杂度很高，会超时。
优化思路：
第一步：一次遍历地图，得出各个岛屿的面积，并做编号记录。可以使用map记录，key为岛屿编号，value为岛屿面积。注意每个节点我们就遍历一次，并不会重复遍历。
第二步：再遍历地图，遍历0的方格（因为要将0变成1），并统计该1（由0变成的1）周边岛屿面积，将其相邻面积相加在一起，遍历所有 0 之后，就可以得出 选一个0变成1 之后的最大面积。
遍历每一个0的方格，并统计其相邻岛屿面积，最后取一个最大值。这里还有一个优化的点，就是 可以不用 visited数组，因为有mark来标记，所以遍历过的grid[i][j]是不等于1的。
package org.example;//具体运行时去掉import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;public class Main {// 四个方向偏移量：右、左、下、上static int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};// 用于在每次 DFS 中累计当前连通岛屿的面积static int count;// 给每个独立岛屿分配唯一标记编号（从2开始，避免与0-水、1-陆地冲突）static int mark;/*** 深度优先搜索：遍历以 (x,y) 为起点的连通陆地* 功能：标记已访问、统计面积、修改网格值为岛屿编号*/public static void dfs(int[][] grid, int x, int y, boolean[][] visited) {// 越界检查：坐标超出网格范围则返回if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length) return;// 若已访问 或 当前格子是海水（0），则停止搜索if (visited[x][y] || grid[x][y] == 0) return;visited[x][y] = true; // 标记为已访问count++; // 当前岛屿面积 +1grid[x][y] = mark; // 将该陆地格子更新为当前岛屿编号// 向四个方向递归扩展for (int i = 0; i < 4; i++) {int nextx = x + dirs[i][0]; // 下一个行坐标int nexty = y + dirs[i][1]; // 下一个列坐标dfs(grid, nextx, nexty, visited); // 继续搜索相邻陆地}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt(); // 输入网格行数int n = sc.nextInt(); // 输入网格列数int[][] grid = new int[m][n]; // 创建 m×n 的地图网格// 输入每个格子的状态：1 表示陆地，0 表示水for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {grid[i][j] = sc.nextInt();}}mark = 2; // 初始化岛屿标记号（0=水，1=原始陆地，2+ 为不同岛屿编号）boolean[][] visited = new boolean[m][n]; // 记录每个格子是否已被 DFS 访问// 哈希表：岛屿标记号 → 对应的面积大小HashMap<Integer, Integer> getSize = new HashMap<>();// 临时集合：记录某个水格子四周相邻的不同岛屿编号（防止重复累加同一岛屿）HashSet<Integer> set = new HashSet<>();// 第一次遍历：识别所有原始陆地岛屿，进行标记和面积统计for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {// 如果是未访问的陆地，则启动 DFSif (grid[i][j] == 1 && !visited[i][j]) {count = 0; // 初始化当前岛屿面积为0dfs(grid, i, j, visited); // 深搜标记整个连通块getSize.put(mark, count); // 存储该岛屿编号及其面积mark++; // 准备下一个岛屿的标记号}}}int result = 0; // 记录能形成的最大岛屿面积（初始化为0）// 关键！！！：将 result 初始化为所有原始岛屿中的最大面积// 防止地图全为陆地时（无海水可填），result 仍能正确反映最大面积for (int size : getSize.values()) {result = Math.max(result, size);}// 第二次遍历：尝试将每个海水格子（0）填为陆地，计算合并后的最大面积for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 0) { // 只处理水格子set.clear(); // 清空集合，用于记录当前格子相邻的不同岛屿int curSize = 1; // 填海后自身变为陆地，面积至少为1// 检查上下左右四个邻居for (int k = 0; k < 4; k++) {int curx = i + dirs[k][0]; // 邻居行坐标int cury = j + dirs[k][1]; // 邻居列坐标// 越界检查if (curx < 0 || curx >= m || cury < 0 || cury >= n) continue;int curMark = grid[curx][cury]; // 获取邻居的岛屿编号// 若该岛屿已统计过，或不是有效岛屿编号（如0水），跳过if (set.contains(curMark) || !getSize.containsKey(curMark)) continue;set.add(curMark); // 记录这个相邻岛屿编号curSize += getSize.get(curMark); // 累加其面积}// 更新全局最大面积result = Math.max(result, curSize);}}}// 输出最终能形成的最大岛屿面积// 包括：原始最大岛屿 或 填海后形成的更大岛屿System.out.println(result);}
}