提示：DDU，供自己复习使用。欢迎大家前来讨论~

图论part03

题目一：101.孤岛的总面积

101. 孤岛的总面积 (kamacoder.com)

解题思路

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

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

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

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

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

DFS

采用深度优先搜索的代码如下：

#include <iostream>
#include <vector>
using namespace std;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四个方向
int count; // 统计符合题目要求的陆地空格数量
void dfs(vector<vector<int>>& grid, int x, int y) {grid[x][y] = 0;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.size() || nexty < 0 || nexty >= grid[0].size()) continue;// 不符合条件，不继续遍历if (grid[nextx][nexty] == 0) continue;dfs (grid, nextx, nexty);}return;
}int main() {int n, m;cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}// 从左侧边，和右侧边 向中间遍历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);}}cout << count << endl;
}

BFS

采用广度优先搜索的代码如下：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int count = 0;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void bfs(vector<vector<int>>& grid, int x, int y) {queue<pair<int, int>> que;que.push({x, y});grid[x][y] = 0; // 只要加入队列，立刻标记count++;while(!que.empty()) {pair<int ,int> cur = que.front(); que.pop();int curx = cur.first;int cury = cur.second;for (int i = 0; i < 4; i++) {int nextx = curx + dir[i][0];int nexty = cury + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过if (grid[nextx][nexty] == 1) {que.push({nextx, nexty});count++;grid[nextx][nexty] = 0; // 只要加入队列立刻标记}}}
}int main() {int n, m;cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}// 从左侧边，和右侧边 向中间遍历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);}}cout << count << endl;
}

题目二：102. 沉没孤岛

102. 沉没孤岛 (kamacoder.com)

解题思路

1. 标记边缘陆地：从地图的边缘开始，将所有边缘的陆地（1）标记为特殊值（2）。
2. 转换中间陆地：遍历整个地图，将未标记的陆地（1）转换为水域（0）。
3. 恢复边缘标记：将特殊标记（2）恢复为陆地（1）。

整体C++代码如下，以下使用dfs实现，其实遍历方式dfs，bfs都是可以的。

#include <iostream>
#include <vector>
using namespace std;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四个方向
void dfs(vector<vector<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.size() || nexty < 0 || nexty >= grid[0].size()) continue;// 不符合条件，不继续遍历if (grid[nextx][nexty] == 0 || grid[nextx][nexty] == 2) continue;dfs (grid, nextx, nexty);}return;
}int main() {int n, m;cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}// 步骤一：// 从左侧边，和右侧边 向中间遍历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++) {cout << grid[i][j] << " ";}cout << endl;}
}

题目三：103. 水流问题

103. 水流问题 (kamacoder.com)

解题思路

想象你有一块高低不平的地形，这块地形是一个由很多小格子组成的矩形，每个小格子都有一个高度值。现在下了一场雨，雨水会从高处流向低处，但是雨水只能流向四个方向：上、下、左、右，而且只能流向比它低或者一样高的地方。

现在，我们要找出那些雨水可以流到地形边缘的格子。地形的边缘分为两组：第一组是地形的左边界和上边界，第二组是右边界和下边界。

任务就是找出所有那些雨水可以流到这两组边界的格子，并输出这些格子的坐标。

（就是找出那些雨水可以流到地形边缘的格子，并告诉你这些格子在哪里。）

1. 输入：你会得到一个矩形矩阵，矩阵的大小由两个数字 N 和 M 决定，N 表示行数，M 表示列数。矩阵中的每个数字代表一个小格子的高度。
2. 输出：你需要找出所有那些雨水可以流到地形的左边界或上边界（第一组边界）的格子，以及所有雨水可以流到地形的右边界或下边界（第二组边界）的格子。然后，你需要输出这些格子的坐标。

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

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

#include <iostream>
#include <vector>
using namespace std;
int n, m;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};// 从 x，y 出发 把可以走的地方都标记上
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& 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);}return;
}
bool isResult(vector<vector<int>>& grid, int x, int y) {vector<vector<bool>> visited(n, vector<bool>(m, false));// 深搜，将x,y出发 能到的节点都标记上。dfs(grid, visited, x, y);bool isFirst = false;bool isSecond = false;// 以下就是判断x，y出发，是否到达第一组边界和第二组边界// 第一边界的上边for (int j = 0; j < m; j++) {if (visited[0][j]) {isFirst = true;break;}}// 第一边界的左边for (int i = 0; i < n; i++) {if (visited[i][0]) {isFirst = true;break;}}// 第二边界右边for (int j = 0; j < m; j++) {if (visited[n - 1][j]) {isSecond = true;break;}}// 第二边界下边for (int i = 0; i < n; i++) {if (visited[i][m - 1]) {isSecond = true;break;}}if (isFirst && isSecond) return true;return false;
}int main() {cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}// 遍历每一个点，看是否能同时到达第一组边界和第二组边界for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (isResult(grid, i, j)) {cout << i << " " << j << endl;}}}
}

直接对每个单元格进行深度优先搜索（DFS）会导致非常高的时间复杂度，尤其是在矩阵较大的情况下。这种直接的DFS方法在最坏情况下的时间复杂度是 $O(m^2\times n^2)$，这对于大型矩阵来说是不可行的。

优化

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

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

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

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

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

按照这样的逻辑，就可以写出如下遍历代码：（详细注释）

#include <iostream>
#include <vector>
using namespace std;
int n, m;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& 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);}return;
}int main() {cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}// 标记从第一组边界上的节点出发，可以遍历的节点vector<vector<bool>> firstBorder(n, vector<bool>(m, false));// 标记从第一组边界上的节点出发，可以遍历的节点vector<vector<bool>> secondBorder(n, vector<bool>(m, false));// 从最上和最下行的节点出发，向高处遍历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]) cout << i << " " << j << endl;;}}}

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

空间复杂度为：O(n * m) 。开了几个 n * m 的数组。

题目四：104.建造最大岛屿

104. 建造最大岛屿 (kamacoder.com)

解题思路

1. 暴力想法：尝试将地图上的每个水域（0）变成陆地（1），然后计算这种情况下的最大岛屿面积。
2. 计算最大面积：通过深度优先搜索（DFS）或广度优先搜索（BFS）遍历地图，标记岛屿，计算面积。这一步的时间复杂度大约是 O($n^2$)，因为需要遍历地图上的每个单元格。
3. 整体时间复杂度：由于地图上有 n2 个单元格，每个单元格改变状态后都需要重新计算最大岛屿面积，所以整体时间复杂度是 O($n^4$)。

优化思路

1. 记录岛屿面积：首先，遍历地图一次，使用深度优先搜索（DFS）找出所有的岛屿，并记录每个岛屿的面积。这一步可以给每个岛屿一个唯一的编号，并使用一个字典（或map）来存储岛屿编号和对应的面积。

2. 计算最大面积：然后，再次遍历地图中的水域（0），对于每个水域单元格，计算它变成陆地（1）后，与它相邻的岛屿面积总和。这样，对于每个水域单元格，你都可以得到一个“潜在的最大面积”，即如果这个水域变成陆地，与它相邻的所有岛屿合并后的总面积。

通过这两步，你可以找到将任意一个水域单元格变成陆地后，能够得到的最大岛屿面积。这种方法避免了重复计算，提高了效率。

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

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

本过程代码如下：

int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& 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.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过dfs(grid, visited, nextx, nexty, mark);}
}int largestIsland(vector<vector<int>>& grid) {int n = grid.size(), m = grid[0].size();vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false)); // 标记访问过的点unordered_map<int ,int> gridNum;int mark = 2; // 记录每个岛屿的编号bool 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); // 将与其链接的陆地都标记上 truegridNum[mark] = count; // 记录每一个岛屿的面积mark++; // 记录下一个岛屿编号}}}
}

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

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

第二步过程如图所示：

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

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

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

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

代码如下：

int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void dfs(vector<vector<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);}
}int main() {cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}unordered_map<int ,int> gridNum;int mark = 2; // 记录每个岛屿的编号bool 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); // 将与其链接的陆地都标记上 truegridNum[mark] = count; // 记录每一个岛屿的面积mark++; // 记录下一个岛屿编号}}}

不过为了让各个变量各司其事，代码清晰一些，完整代码还是使用visited数组来标记。

最后，整体代码如下：

#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
using namespace std;
int n, m;
int count;int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& 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);}
}int main() {cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}vector<vector<bool>> visited(n, vector<bool>(m, false)); // 标记访问过的点unordered_map<int ,int> gridNum;int mark = 2; // 记录每个岛屿的编号bool 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); // 将与其链接的陆地都标记上 truegridNum[mark] = count; // 记录每一个岛屿的面积mark++; // 记录下一个岛屿编号}}}if (isAllGrid) {cout << n * m << endl; // 如果都是陆地，返回全面积return 0; // 结束程序}// 以下逻辑是根据添加陆地的位置，计算周边岛屿面积之和int result = 0; // 记录最后结果unordered_set<int> visitedGrid; // 标记访问过的岛屿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.count(grid[neari][nearj])) continue; // 添加过的岛屿不要重复添加// 把相邻四面的岛屿数量加起来count += gridNum[grid[neari][nearj]];visitedGrid.insert(grid[neari][nearj]); // 标记该岛屿已经添加过}}result = max(result, count);}}cout << result << endl;}

总结

坚持！！！