代码随想录Day52 101. 孤岛的总面积，102. 沉没孤岛，103. 水流问题，104.建造最大岛屿。

1.孤岛的总面积

卡码网：101. 孤岛的总面积(opens new window)

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。

现在你需要计算所有孤岛的总面积，岛屿面积的计算方式为组成岛屿的陆地的总数。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0。

输出描述

输出一个整数，表示所有孤岛的总面积，如果不存在孤岛，则输出 0。

输入示例

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

输出示例：

1

提示信息：

在矩阵中心部分的岛屿，因为没有任何一个单元格接触到矩阵边缘，所以该岛屿属于孤岛，总面积为 1。

数据范围：

1 <= M, N <= 50。

思路

本题使用dfs，bfs，并查集都是可以的。

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

如图，在遍历地图周围四个边，靠地图四边的陆地，都为绿色，

在遇到地图周边陆地的时候，将1都变为0，此时地图为这样：

然后我们再去遍历这个地图，遇到有陆地的地方，去采用深搜或者广搜，边统计所有陆地。

如果对深搜或者广搜不够了解，建议先看这里：深度优先搜索精讲，广度优先搜索精讲。

public class Total_Area_of_Isolated_Islands {private static int count = 0;//用于存储所有孤岛的总面积。private static final int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};//定义了四个方向的移动，分别对应下、右、上、左。private static void bfs(int[][] grid, int x, int y) {//私有静态方法，用于执行广度优先搜索。int[][] grid 是输入的二维数组，表示地图，其中1表示陆地，0表示水域。int x 和 int y 是当前单元格的坐标。Queue<int[]> que = new LinkedList<>();que.add(new int[]{x, y});//将起始坐标加入队列，并将其标记为已访问（将grid[x][y]设置为0）。grid[x][y] = 0;//不断从队列中取出坐标，对其四个相邻单元格进行检查。如果相邻单元格是陆地（值为1）且未被访问过，则将其加入队列，标记为已访问，并增加count。count++;//一直持续到队列为空，即当前岛屿的所有相连陆地单元格都被访问过。while (!que.isEmpty()) {int[] cur = que.poll();int curx = cur[0];int cury = cur[1];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) {que.add(new int[]{nextx, nexty});count++;grid[nextx][nexty] = 0;}}}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();//使用Scanner类从标准输入读取数据。首先读取两个整数n和m，分别代表地图的行数和列数。创建一个大小为n x m的二维数组grid，用于存储地图数据。循环读取n x m个整数填充grid。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();}//接下来，程序检查地图的边界上的陆地单元格，并对其执行BFS，以确保边界上的陆地不被重复计算。重置count为0，然后遍历整个地图，对所有未访问的陆地单元格执行BFS，计算每个孤岛的面积。最后，输出所有孤岛的总面积。}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);}
}

• 时间复杂度：O(n * m)，其中n和m分别是地图的行数和列数。
  • 程序需要遍历整个地图，对每个单元格进行一次检查。
  • 对于每个陆地单元格，BFS操作最多需要访问其四个邻居，因此总体时间复杂度与地图大小成正比。
• 空间复杂度：O(n * m)，主要由于队列的空间需求。
  • 在最坏的情况下，队列可能需要存储整个地图的陆地单元格，这需要O(n * m)的空间。
  • 此外，count变量和dir数组占用的空间是常数级别的，可以忽略不计。

2.沉没孤岛

卡码网题目链接（ACM模式）(opens new window)

题目描述：

给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。

现在你需要将所有孤岛“沉没”，即将孤岛中的所有陆地单元格（1）转变为水域单元格（0）。

输入描述：

第一行包含两个整数 N, M，表示矩阵的行数和列数。

之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

输出描述

输出将孤岛“沉没”之后的岛屿矩阵。

输入示例：

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

输出示例：

1 1 0 0 0
1 1 0 0 0
0 0 0 0 0
0 0 0 1 1

提示信息：

将孤岛沉没：

数据范围：

1 <= M, N <= 50

思路

这道题目和0101.孤岛的总面积 (opens new window)正好反过来了，0101.孤岛的总面积 (opens new window)是求 地图中间的空格数，而本题是要把地图中间的 1 都改成 0 。

那么两题在思路上也是差不多的。

思路依然是从地图周边出发，将周边空格相邻的陆地都做上标记，然后在遍历一遍地图，遇到 陆地 且没做过标记的，那么都是地图中间的 陆地 ，全部改成水域就行。

有的录友可能想，我在定义一个 visited 二维数组，单独标记周边的陆地，然后遍历地图的时候同时对 数组board 和 数组visited 进行判断，决定 陆地是否变成水域。

这样做其实就有点麻烦了，不用额外定义空间了，标记周边的陆地，可以直接改陆地为其他特殊值作为标记。

步骤一：深搜或者广搜将地图周边的 1 （陆地）全部改成 2 （特殊标记）

步骤二：将水域中间 1 （陆地）全部改成 水域（0）

步骤三：将之前标记的 2 改为 1 （陆地）

如图：

 

public class Sunken_Island {static int[][] dir = { {-1, 0}, {0, -1}, {1, 0}, {0, 1} };//定义了四个方向的移动，分别对应上、左、下、右。public static void dfs(int[][] grid, int x, int y) {//一个递归方法，用于深度优先搜索。int[][] grid 是输入的二维数组，表示地图。int x 和 int y 是当前单元格的坐标。grid[x][y] = 2;//先将当前土地格标记为2，表示已访问。for (int[] d : dir) {//对当前坐标的四个相邻单元格进行搜索，如果相邻单元格是土地（值为1）且未被访问过，则递归调用dfs方法。int nextX = x + d[0];int nextY = y + d[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);//如果相邻单元格是水域（值为0）或已访问的土地（值为2），则跳过。}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);//使用Scanner类从标准输入读取数据。首先读取两个整数n和m，分别代表地图的行数和列数。创建一个大小为n x m的二维数组grid，用于存储地图数据。循环读取n x m个整数填充grid。int n = scanner.nextInt();int m = scanner.nextInt();int[][] grid = new int[n][m];for (int i = 0; i < n; i++) {//对地图的边界土地格执行DFS，将与边界相连的土地格标记为2。遍历整个地图，将所有标记为1的土地格变为0，将标记为2的土地格恢复为1，从而实现沉没孤岛的效果。最后，输出变换后的地图。for (int j = 0; j < m; j++) {grid[i][j] = scanner.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();}scanner.close();}
}

• 时间复杂度：O(n * m)，其中n和m分别是地图的行数和列数。
  • 程序需要遍历整个地图，对每个单元格进行一次检查。
  • 对于每个土地单元格，DFS操作最多需要访问其四个邻居，因此总体时间复杂度与地图大小成正比。
• 空间复杂度：O(n * m)，主要由于递归栈的空间需求。
  • 在最坏的情况下，递归栈可能需要存储整个地图的土地单元格，这需要O(n * m)的空间。
  • 此外，dir数组占用的空间是常数级别的，可以忽略不计。

3.水流问题

卡码网题目链接（ACM模式）(opens new window)

题目描述：

现有一个 N × M 的矩阵，每个单元格包含一个数值，这个数值代表该位置的相对高度。矩阵的左边界和上边界被认为是第一组边界，而矩阵的右边界和下边界被视为第二组边界。

矩阵模拟了一个地形，当雨水落在上面时，水会根据地形的倾斜向低处流动，但只能从较高或等高的地点流向较低或等高并且相邻（上下左右方向）的地点。我们的目标是确定那些单元格，从这些单元格出发的水可以达到第一组边界和第二组边界。

输入描述：

第一行包含两个整数 N 和 M，分别表示矩阵的行数和列数。

后续 N 行，每行包含 M 个整数，表示矩阵中的每个单元格的高度。

输出描述：

输出共有多行，每行输出两个整数，用一个空格隔开，表示可达第一组边界和第二组边界的单元格的坐标，输出顺序任意。

输入示例：

5 5
1 3 1 2 4
1 2 1 3 2
2 4 7 2 1
4 5 6 1 1
1 4 1 2 1

输出示例：

0 4
1 3
2 2
3 0
3 1
3 2
4 0
4 1

提示信息：

图中的蓝色方块上的雨水既能流向第一组边界，也能流向第二组边界。所以最终答案为所有蓝色方块的坐标。

数据范围：

1 <= M, N <= 50

思路

一个比较直白的想法，其实就是 遍历每个点，然后看这个点 能不能同时到达第一组边界和第二组边界。

至于遍历方式，可以用dfs，也可以用bfs，以下用dfs来举例。

遍历每一个节点，是 m * n，遍历每一个节点的时候，都要做深搜，深搜的时间复杂度是： m * n

那么整体时间复杂度 就是 O(m^2 * n^2) ，这是一个四次方的时间复杂度。

优化

那么我们可以 反过来想，从第一组边界上的节点 逆流而上，将遍历过的节点都标记上。

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

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

从第一组边界边上节点出发，如图：

从第二组边界上节点出发，如图：

时间复杂度分析， 关于dfs函数搜索的过程 时间复杂度是 O(n * m)，这个大家比较容易想。

关键看主函数，那么每次dfs的时候，上面还是有for循环的。

第一个for循环，时间复杂度是：n * (n * m) 。

第二个for循环，时间复杂度是：m * (n * m)。

所以本题看起来 时间复杂度好像是 ： n * (n * m) + m * (n * m) = (m * n) * (m + n) 。

其实这是一个误区，大家再自己看 dfs函数的实现，其实 有visited函数记录 走过的节点，而走过的节点是不会再走第二次的。

所以 调用dfs函数，只要参数传入的是 数组 firstBorder，那么地图中 每一个节点其实就遍历一次，无论你调用多少次。

同理，调用dfs函数，只要 参数传入的是 数组 secondBorder，地图中每个节点也只会遍历一次。

所以，以下这段代码的时间复杂度是 2 * n * m。 地图用每个节点就遍历了两次，参数传入 firstBorder 的时候遍历一次，参数传入 secondBorder 的时候遍历一次。

本题整体的时间复杂度其实是： 2 * n * m + n * m ，所以最终时间复杂度为 O(n * m) 。

空间复杂度为：O(n * m) 这个就不难理解了。开了几个 n * m 的数组。

public class Water_Flow_Problem {public static void dfs(int[][] heights, int x, int y, boolean[][] visited, int preH) {//递归方法，用于执行深度优先搜索。int[][] heights 是输入的二维数组，表示地形的高度图。int x 和 int y 是当前单元格的坐标。boolean[][] visited 是一个布尔数组，用来标记某个单元格是否已经被访问过。int preH 是前一个单元格的高度，用于判断当前单元格是否为低洼地带，即水流可以流向的地方。if (x < 0 || x >= heights.length || y < 0 || y >= heights[0].length || visited[x][y]) return;//检查当前坐标是否越界或已被访问，如果是，则返回。if (heights[x][y] < preH) return;//如果当前单元格的高度小于前一个单元格的高度，说明水流可以流向这里，将当前单元格标记为已访问，并递归地对四个相邻单元格进行搜索。visited[x][y] = true;dfs(heights, x + 1, y, visited, heights[x][y]);dfs(heights, x - 1, y, visited, heights[x][y]);dfs(heights, x, y + 1, visited, heights[x][y]);dfs(heights, x, y - 1, visited, heights[x][y]);}public static void main(String[] args) {Scanner sc = new Scanner(System.in);//使用Scanner类从标准输入读取数据。首先读取两个整数m和n，分别代表地图的行数和列数。创建一个大小为m x n的二维数组heights，用于存储地图的高度数据。循环读取m x n个整数填充heights。创建两个布尔数组pacific和atlantic，分别用来标记单元格是否能够被太平洋和大西洋流入。int m = sc.nextInt();int n = sc.nextInt();int[][] heights = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {heights[i][j] = sc.nextInt();}//对地图的所有边界单元格执行DFS，从太平洋（左边界和上边界）开始，将能够流入的单元格标记为true在pacific数组中；从大西洋（右边界和下边界）开始，将能够流入的单元格标记为true在atlantic数组中。}boolean[][] pacific = new boolean[m][n];boolean[][] atlantic = new boolean[m][n];for (int i = 0; i < m; i++) {dfs(heights, i, 0, pacific, Integer.MIN_VALUE);dfs(heights, i, n - 1, atlantic, Integer.MIN_VALUE);}for (int j = 0; j < n; j++) {dfs(heights, 0, j, pacific, Integer.MIN_VALUE);dfs(heights, m - 1, j, atlantic, Integer.MIN_VALUE);}List<List<Integer>> res = new ArrayList<>();//创建一个列表res，用于存储同时能够被太平洋和大西洋流入的单元格的坐标。for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (pacific[i][j] && atlantic[i][j]) {res.add(Arrays.asList(i, j));}}}//遍历整个地图，如果一个单元格在pacific和atlantic数组中都被标记为true，则将其坐标添加到res列表中。最后，遍历res列表，打印出所有同时能够被太平洋和大西洋流入的单元格的坐标。for (List<Integer> list : res) {for (int k = 0; k < list.size(); k++) {if (k == 0) {System.out.print(list.get(k) + " ");} else {System.out.print(list.get(k));}}System.out.println();}}
}

• 时间复杂度：O(m * n)，其中m和n分别是地图的行数和列数。
  • 程序需要遍历整个地图，对每个单元格进行一次检查。
  • 对于每个单元格，DFS操作最多需要访问其四个邻居，因此总体时间复杂度与地图大小成正比。
• 空间复杂度：O(m * n)，主要由于递归栈的空间需求和两个布尔数组pacific和atlantic。
  • 在最坏的情况下，递归栈可能需要存储整个地图的单元格，这需要O(m * n)的空间。
  • 两个布尔数组pacific和atlantic也需要O(m * n)的空间。

4.建造最大岛屿

卡码网题目链接（ACM模式）(opens new window)

题目描述：

给定一个由 1（陆地）和 0（水）组成的矩阵，你最多可以将矩阵中的一格水变为一块陆地，在执行了此操作之后，矩阵中最大的岛屿面积是多少。

岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿是被水包围，并且通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设矩阵外均被水包围。

输入描述：

第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

输出描述：

输出一个整数，表示最大的岛屿面积。

输入示例：

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

输出示例

6

提示信息

对于上面的案例，有两个位置可将 0 变成 1，使得岛屿的面积最大，即 6。

数据范围：

1 <= M, N <= 50。

思路

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

计算地图的最大面积：遍历地图 + 深搜岛屿，时间复杂度为 n * n。

（其实使用深搜还是广搜都是可以的，其目的就是遍历岛屿做一个标记，相当于染色，那么使用哪个遍历方式都行，以下我用深搜来讲解）

每改变一个0的方格，都需要重新计算一个地图的最大面积，所以 整体时间复杂度为：n^4。

优化思路

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

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

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

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

拿如下地图的岛屿情况来举例： （1为陆地）

第一步，则遍历题目，并将岛屿到编号和面积上的统计，过程如图所示：

这个过程时间复杂度 n * n 。可能有录友想：分明是两个for循环下面套这一个dfs，时间复杂度怎么回事 n * n呢？

其实大家可以仔细看一下代码，n * n这个方格地图中，每个节点我们就遍历一次，并不会重复遍历。

第二步过程如图所示：

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

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

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

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

public class Maximize_the_Area_of_an_Island {static int count;//用于在DFS过程中计数岛屿的大小。static int mark;//用于标记新发现的岛屿，以便在哈希表中区分。static int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};//定义了四个方向的移动，分别对应下、上、右、左。public static void dfs(int[][] grid, int x, int y, boolean[][] visited) {//个递归方法，用于执行深度优先搜索，计算单个岛屿的面积。int[][] grid 是输入的二维数组，表示地图。int x 和 int y 是当前单元格的坐标。boolean[][] visited 是一个布尔数组，用来标记某个单元格是否已经被访问过。if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length) return;//检查当前坐标是否越界或已被访问，如果是，则返回。if (visited[x][y] || grid[x][y] == 0) return;//如果当前单元格是陆地（grid[x][y] == 1），则将其标记为已访问，并增加岛屿计数。visited[x][y] = true;count++;grid[x][y] = mark;//然后，方法递归地对当前坐标的四个相邻单元格进行搜索，以找到整个岛屿。dfs(grid, x, y + 1, visited);dfs(grid, x, y - 1, visited);dfs(grid, x + 1, y, visited);dfs(grid, x - 1, y, visited);}public static void main (String[] args) {Scanner sc = new Scanner(System.in);//使用Scanner类从标准输入读取数据。首先读取两个整数m和n，分别代表地图的行数和列数。创建一个大小为m x n的二维数组grid，用于存储地图数据。循环读取m x n个整数填充grid。初始化mark为2，visited数组用于跟踪访问过的单元格。int m = sc.nextInt();int n = sc.nextInt();int[][] grid = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {grid[i][j] = sc.nextInt();}}mark = 2;boolean[][] visited = new boolean[m][n];HashMap<Integer, Integer> getSize = new HashMap<>();//创建一个HashMap<Integer, Integer> getSize来存储每个岛屿的面积，键是岛屿的标记，值是面积。HashSet<Integer> set = new HashSet<>();//创建一个HashSet<Integer> set来存储已经考虑过的岛屿标记，避免重复计算。boolean isAllIsland = true;//遍历整个地图，对每个陆地单元格执行DFS，计算岛屿面积，并更新getSize。for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 0) isAllIsland = false;if (grid[i][j] == 1) {count = 0;dfs(grid, i, j, visited);getSize.put(mark, count);mark++;}}}int result = 0;//初始化result为0，用于存储最大可能的岛屿面积。如果整个网格都是陆地（即isAllIsland为true），则最大岛屿面积就是整个网格的面积。if (isAllIsland) result =  m * n;for (int i = 0; i < m; i++) {//遍历整个地图，对每个水单元格，检查将其变为陆地后，周围岛屿的总面积，并更新result。最后，输出计算出的最大岛屿面积。for (int j = 0; j < n; j++) {if (grid[i][j] == 0) {set.clear();int curSize = 1;for (int[] dir : dirs) {int curRow = i + dir[0];int curCol = j + dir[1];if (curRow < 0 || curRow >= m || curCol < 0 || curCol >= n) continue;int curMark = grid[curRow][curCol];if (set.contains(curMark) || !getSize.containsKey(curMark)) continue;set.add(curMark);curSize += getSize.get(curMark);}result = Math.max(result, curSize);}}}System.out.println(result);}
}

 

• 时间复杂度：O(m * n)，其中m和n分别是地图的行数和列数。
  • 程序需要遍历整个地图，对每个单元格进行一次检查。
  • 对于每个陆地单元格，DFS操作最多需要访问其四个邻居，因此总体时间复杂度与地图大小成正比。
• 空间复杂度：O(m * n)，主要由于递归栈的空间需求和visited数组。
  • 在最坏的情况下，递归栈可能需要存储整个地图的单元格，这需要O(m * n)的空间。
  • visited数组也需要O(m * n)的空间。
  • getSize哈希表在最坏情况下也需要O(m * n)的空间，因为每个岛屿都可能有一个唯一的标记。