深度优先搜索解决岛屿类问题

0 更新记录

2024-09-10: 初始版本

给最近刷到的LeetCode上用深度优先搜索（Depth First Search, DFS）解决的岛屿类问题做个总结。

所有的岛屿类问题可以总结为对二维矩阵的遍历，一般需要寻找连通的区域，相邻格点一般为上下左右4个，这种类型的题目使用DFS是一个比较通用的方法。

1 题目列表

LeetCode题目链接	本文小节链接
200.岛屿数量	200.岛屿数量
463.岛屿的周长	463.岛屿的周长
695.岛屿的最大面积	695.岛屿的最大面积
1254.统计封闭岛屿的数目	1254.统计封闭岛屿的数目
1905.统计子岛屿	1905.统计子岛屿
1020.飞地的数量	1020.飞地的数量
827.最大人工岛	827.最大人工岛

2 题解

200.岛屿数量

思路

遍历整张图，遇到陆地格点后，将与这个格点连通的区域（题目中定义的岛屿）标记为已经访问过，这个过程使用DFS完成。

下次再遇到陆地格点时，检查是否已经被标记为访问过，如果是未访问的格点，说明是一块新的陆地，记录到岛屿数量中，然后将这片岛屿标记为已访问。

不断重复这个过程，直到整张图都被遍历完，就得到了连通区域的数量。

实现细节

以下代码中，使用了vector<vector<bool>> visited数组来标记(i, j)位置的格点是否被访问过。

主函数中，遍历所有格点，如果遇到未被标记的陆地格点，则使用DFS递归函数将与这一格点相连的陆地标记为已访问，将岛屿数量的计数加一。

在DFS递归函数中，传入的位置(i, j)越过边界、是海洋格点或者被标记为已访问，就需要返回退出。这三个条件都是必须要判断的，虽然在主函数中进行了“未被标记的陆地格点”的判断，但是DFS函数是递归调用的，并不总是从主函数进入，所以主函数判断的结果并不总是满足。

代码

class Solution {
public:
    void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int i, int j) {
        int m = grid.size();
        int n = grid[0].size();
        // 越过边界
        if(i < 0 || j < 0 || i >= m || j >= n) return;
        // 是海洋，退出
        if(grid[i][j] == '0') return;
        // 已经访问过，退出
        if(visited[i][j]) return;
        // 标记访问
        visited[i][j] = true;
        // 向四周搜素，将与当前点相连的陆地全部标记已访问
        dfs(grid, visited, i - 1, j);
        dfs(grid, visited, i + 1, j);
        dfs(grid, visited, i, j - 1);
        dfs(grid, visited, i, j + 1);
    }
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int result = 0;
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(visited[i][j] == false && grid[i][j] == '1') {
                    result++;
                    dfs(grid, visited, i, j);
                }
            }
        }
        return result;
    }
};

优化代码

题目并没有限制对传入的参数gird是否可以被修改，所以可以充分利用这个空间标记是否已经访问过，从而省去创建visited数组的开销。在需要标记为已访问的位置(i, j)将grid[i][j]修改为其他值可以表示其已经被访问。更简单的做法是直接修改为'0'，将陆地变为海洋，这样还可以简化DFS代码中的递归返回条件的判断。修改优化后的代码：

class Solution {
public:
    void dfs(vector<vector<char>>& grid, int i, int j) {
        int m = grid.size();
        int n = grid[0].size();
        // 越过边界
        if(i < 0 || j < 0 || i >= m || j >= n) return;
        // 是海洋或者已访问，退出
        if(grid[i][j] == '0') return;
        // 标记访问
        grid[i][j] = '0';
        // 向四周搜素，将与当前点相连的陆地全部标记已访问
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int result = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == '1') {
                    result++;
                    dfs(grid, i, j);
                }
            }
        }
        return result;
    }
};

463.岛屿的周长

思路

仍然是对二维矩阵的遍历，只是遍历过程中需要记录边长总和。

对于每一个陆地格点来说，先考虑最基本的某一个方向，并且不能重复访问已经访问过的格点。

当从陆地格点进入下一个陆地格点后，前进的方向没有产生新的边长，因为两块陆地之间的边长并不是岛屿的边长，注意再次说明这里只考虑前进方向这一条边的有无，其他三个方向在向对应方向前进时再统计。

如果进入的下一个格点超出了边界，说明当前的格点就是地图最外侧的陆地格点，前进方向的边应当作为岛屿的边来计算。

同理从当前陆地格点前进到了海洋格点，此时跨过的边也是岛屿的一条边，也需要计入周长。

实现细节

与上一题目类似，主函数还是找一个陆地点，使用DFS搜索。实际上这个题目已经说明只有一个岛屿，所以从主函数只会进入一次DFS函数，实际上从任意一个陆地点(i, j)进入DFS函数都能得到正确的结果。

DFS函数与之前有个明显的不同是有了返回值，含义是返回与(i, j)位置的陆地点相连的岛屿的边长。

递归结束条件为之前分析的三种岛屿的边界，对于从陆地进入地图边界和从陆地到海洋这两种情况，当前格点向岛屿贡献的边长增加一条；

对于进入了已经标记为已访问的格点，直接退出并且不新增岛屿的边长。

对于进入了未被标记的陆地点，也不产生边长，此时需要将这个陆地点标记为已访问，并在这个陆地点重复上面的向四周前进并判断的过程（递归调用DFS），并将这个陆地点四周的点的边长贡献总和返回。

代码

class Solution {
public:
    int dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int i, int j) {
        int m = grid.size();
        int n = grid[0].size();
        // 岛屿 -> 边界之外，产生一条边
        if(i < 0 || j < 0 || i >= m || j >= n) return 1;
        // 已经访问过，直接退出不产生边
        if(visited[i][j]) return 0;
        // 岛屿 -> 海洋，产生一条边
        if(grid[i][j] == 0) return 1;
        // 仍是岛屿
        visited[i][j] = true;
        return (dfs(grid, visited, i - 1, j) + dfs(grid, visited, i + 1, j) + dfs(grid, visited, i, j - 1) +
                dfs(grid, visited, i, j + 1));
    }
    int islandPerimeter(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1)
                    // 从任意一个岛屿点开始搜索
                    return dfs(grid, visited, i, j);
            }
        }
        return 0;
    }
};

优化代码

与200.岛屿数量的优化思路类似，可以对grid修改避免使用visited数组，在后续的题目中，如果可以“复用”grid数组，则都不会再使用visited数组。

以下是优化后的方法：

class Solution {
public:
    int dfs(vector<vector<int>>& grid, int i, int j) {
        int m = grid.size();
        int n = grid[0].size();
        // 岛屿 -> 边界之外，产生一条边
        if(i < 0 || j < 0 || i >= m || j >= n) return 1;
        // 已经访问过，直接退出不产生边
        if(grid[i][j] == 2) return 0;
        // 岛屿 -> 海洋，产生一条边
        if(grid[i][j] == 0) return 1;
        // 仍是岛屿
        grid[i][j] = 2;
        return (dfs(grid, i - 1, j) + dfs(grid, i + 1, j) + dfs(grid, i, j - 1) + dfs(grid, i, j + 1));
    }
    int islandPerimeter(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1)
                    // 从任意一个岛屿点开始搜索
                    return dfs(grid, i, j);
            }
        }
        return 0;
    }
};

模拟方法

这个题目还有更为直观的模拟方法，其实个人觉得模拟方法解决这道题更简单易懂，使用DFS有点“没苦硬吃”的感觉。

模拟的思路就是对于一个孤立的陆地格点，它应当拥有四条边。当这个格点上侧有陆地时，就会少一条边；同理其他三个方向都是这种情况。getBorder函数用于计算传入位置格点能贡献给周长的边数。注意在判断四个相邻点时要先检查索引是否越界。位于边界的边不需要减少，所以边界点和内部点的判断逻辑相同。

主函数中累加每个陆地格点能贡献给岛屿周长的边的数量。

class Solution {
public:
    int getBorder(vector<vector<int>>& grid, int i, int j) {
        int result = 4;
        if(i > 0 && grid[i - 1][j] == 1) result--;
        if(i < grid.size() - 1 && grid[i + 1][j] == 1) result--;
        if(j > 0 && grid[i][j - 1] == 1) result--;
        if(j < grid[0].size() - 1 && grid[i][j + 1] == 1) result--;
        return result;
    }
    int islandPerimeter(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int result = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1) result += getBorder(grid, i, j);
            }
        }
        return result;
    }
};

695.岛屿的最大面积

思路

需要在DFS搜索陆地点构成的岛屿时计算岛屿的面积，参考463.岛屿的周长中使用DFS遍历同时计算周长的思路，可以得到如下结果：

从陆地点越过边界：不新增面积
从陆地点进入海洋：不新增面积
从陆地点进入已访问的陆地：不新增面积
从陆地点进入未访问的陆地：新增当前点的面积1，并从当前点继续向四周前进

实现细节

主函数需要维护一个最大面积，遍历每个未被访问的陆地点，然后使用DFS函数计算与这个陆地点相连的岛屿的面积，并将这个岛屿所有点标记为已访问。

DFS递归结束条件为上面分析的三种情况，当前点(i, j)为边界之外、海洋或已访问过的点时，都不新增面积，直接返回0。

每次进入DFS函数时，一定是从陆地点进入的，也就是说当前点(i, j)的上一步一定也是陆地点，如果不是，那么在上一步不是陆地点的时候就会退出递归过程。所以在之前分析各种情况时都是“从陆地点进入……”
这里使用了修改grid来标记已访问，所以grid[i][j] == 0既可能是海洋也可能是已访问的陆地。

当前点为未访问的陆地，标记访问后，向四周搜索并向上一级返回四周点能够能贡献的面积，加上自己能提供的面积1。

代码

class Solution {
public:
    // 返回与当前土地点相连的未访问的岛屿的面积
    int dfs(vector<vector<int>>& grid, int i, int j) {
        int m = grid.size();
        int n = grid[0].size();
        // 岛屿 -> 边界之外，不产生面积
        if(i < 0 || j < 0 || i >= m || j >= n) return 0;
        // 进入海洋或者已经访问过，不产生面积
        if(grid[i][j] == 0) return 0;
        // 将当前点标记为已访问
        grid[i][j] = 0;
        // 向四周搜索，返回自身的面积1+四周的面积
        return (1 + dfs(grid, i - 1, j) + dfs(grid, i + 1, j) + dfs(grid, i, j - 1) + dfs(grid, i, j + 1));
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int result = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1) {
                    result = max(result, dfs(grid, i, j));
                }
            }
        }
        return result;
    }
};

1254.统计封闭岛屿的数目

思路

直接去判断岛屿封闭的情况想起来可能比较复杂，这时候可以考虑“正难则反”的思路。

封闭岛屿的数量 = 总岛屿数量 - 不封闭岛屿的数量

岛屿的总数是容易计算的，在200.岛屿数量中已经计算过。不封闭岛屿是什么呢，就是和边界直接相连的岛屿。

明确了这个情况之后就可以将思路转化为，先排除掉不封闭的岛屿（将其标记为已经访问），然后再遍历全图计算得到的所有岛屿数量就是封闭岛屿数量。

实现细节

主函数中先将与四条边界相连的岛屿用DFS函数标记为已访问的岛屿，然后对全图的未访问的陆地点使用DFS搜索，此处就完全转换为200.岛屿数量中的问题。

DFS实现和200.岛屿数量的优化代码完全一致，只是题目对陆地和海洋的定义相反，本题中陆地用0表示，海洋用1表示。

代码

class Solution {
public:
    void dfs(vector<vector<int>>& grid, int i, int j) {
        int m = grid.size();
        int n = grid[0].size();
        // 越过边界
        if(i < 0 || j < 0 || i >= m || j >= n) return;
        // 是海洋或者已访问，退出
        if(grid[i][j] == 1) return;
        // 标记访问
        grid[i][j] = 1;
        // 向四周搜素，将与当前点相连的陆地全部标记已访问
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }
    int closedIsland(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int result = 0;
        // 将边界的岛屿都标记为访问过(变成海洋)
        for(int i = 0; i < m; i++) {
            dfs(grid, i, 0);
            dfs(grid, i, n - 1);
        }
        for(int j = 0; j < n; j++) {
            dfs(grid, 0, j);
            dfs(grid, m - 1, j);
        }
        // 统计封闭岛屿数量
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 0) {
                    result++;
                    dfs(grid, i, j);
                }
            }
        }
        return result;
    }
};

1905.统计子岛屿

思路

本题部分延续了上一题1254.统计封闭岛屿的数目中“正难则反”的思路，直接去考虑两张图的包含关系可能不是很好判断，那么可以考虑：

先把不可能是grid1子岛屿的岛屿部分从grid2中剔除，也就是标记为已访问，然后问题再次转化为计算grid2中岛屿的数量。

如何判断grid2中哪些岛屿一定不是grid1的子岛屿呢？子岛屿要求满足完全包含，所以只要有一个格点不包含，那就一定不是子岛屿。

也就是说，如果grid2中的一个格点是陆地，但同位置的grid1是海洋，这个位置就一定不属于子岛屿，和这个位置相连的陆地也不可能是子岛屿。

实现细节

主函数中首先对grid2中是陆地但grid1中是水的所有格点用DFS标记，标记为已经访问的区域会在后序搜索中被剔除。然后问题转化为计算grid2中的岛屿数量，与200.岛屿数量完全相同。

DFS函数实现和200.岛屿数量完全一致。

代码

class Solution {
public:
    void dfs(vector<vector<int>>& grid, int i, int j) {
        int m = grid.size();
        int n = grid[0].size();
        // 越过边界
        if(i < 0 || j < 0 || i >= m || j >= n) return;
        // 是海洋或者已访问，退出
        if(grid[i][j] == 0) return;
        // 标记访问
        grid[i][j] = 0;
        // 向四周搜素，将与当前点相连的陆地全部标记已访问
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        int m = grid2.size();
        int n = grid2[0].size();
        // 先标记剔除不可能是子岛屿的岛屿
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                // grid2中是陆地但grid1中是水
                if(grid2[i][j] == 1 && grid1[i][j] == 0) {
                    dfs(grid2, i, j);
                }
            }
        }
        // grid2中剩下的岛屿都是子岛屿
        int result = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid2[i][j] == 1) {
                    result++;
                    dfs(grid2, i, j);
                }
            }
        }
        return result;
    }
};

1020.飞地的数量

思路

本题可以认为是1254.统计封闭岛屿的数目和695.岛屿的最大面积的一个缝合。

题目中的飞地描述为“无法在任意次数的移动中离开网格边界的陆地”即1254.统计封闭岛屿的数目中对封闭岛屿的定义，本题要计算这种“陆地单元格的数量”，也就是计算封闭岛屿的面积。

寻找飞地使用封闭岛屿的思路，先把四周的边界处的陆地标记为已访问的区域，然后遍历整张图，使用计算岛屿面积的算法得到飞地的单元格数量。

实现细节

主函数与1254.统计封闭岛屿的数目的主函数相同；DFS递归函数与695.岛屿的最大面积的DFS函数。

需要注意本题使用0表示一个海洋单元格、1表示一个陆地单元格。

代码

class Solution {
public:
    int dfs(vector<vector<int>>& grid, int i, int j) {
        int m = grid.size();
        int n = grid[0].size();
        // 越过边界
        if(i < 0 || j < 0 || i >= m || j >= n) return 0;
        // 是海洋或者已访问，退出
        if(grid[i][j] == 0) return 0;
        // 标记访问
        grid[i][j] = 0;
        // 向四周搜素，将与当前点相连的陆地全部标记已访问
        return (1 + dfs(grid, i - 1, j) + dfs(grid, i + 1, j) + dfs(grid, i, j - 1) + dfs(grid, i, j + 1));
    }
    int numEnclaves(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int result = 0;
        // 将边界的飞地都标记为访问过(变成海洋)，且不需要保留返回的面积
        for(int i = 0; i < m; i++) {
            dfs(grid, i, 0);
            dfs(grid, i, n - 1);
        }
        for(int j = 0; j < n; j++) {
            dfs(grid, 0, j);
            dfs(grid, m - 1, j);
        }
        // 统计封闭岛屿（飞地）的面积
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1) {
                    result += dfs(grid, i, j);
                }
            }
        }
        return result;
    }
};

827.最大人工岛

思路

最为直接的暴力思路是，尝试将每个海洋格点修改为陆地格点，然后计算修改后的岛屿面积，并在计算过程中维护岛屿的最大值。不过这个思路由于每次都要重新计算整张图的岛屿面积，时间复杂度高达 $O \left(n^4 \right)$ ，对于本题n <= 500的数据量是一定会超时的。时间复杂度高的原因就是，每修改一个点，只影响到了这个点周边的最多四块岛屿的面积，却要对整张图的岛屿面积重复计算。

对于每个海洋格点遍历 $O \left( n \times n \right)$，都计算其修改为陆地后的最大岛屿面积 $O \left(n \times n \right)$，总时间复杂度 $O \left(n^4 \right)$

为了减少岛屿面积的重复计算，可以先计算所有岛屿的面积并保存，然后尝试将每个海洋格点变为陆地，计算这个格点周围的岛屿面积时，使用之前计算的结果，而不再重新DFS搜索计算面积。此时的总时间复杂度是$O \left(n^2 \right)$，是能够满足要求的。

计算所有岛屿面积 $O \left( n^2 \right)$，修改每个海洋格点 $O \left( n^2 \right)$，由于这个算法中这两步是先后进行的，而不是像之前一样嵌套执行，所以总时间复杂度是 $O \left(n^2 + n^2 \right)$，时间复杂度一般不考虑常系数，所以这个思路最终的时间复杂度为$O \left(n^2 \right)$

接下来的关键问题在于如何保存岛屿面积，还需要区分不同的岛屿，区分岛屿可以为不同的岛屿编号。同时保存这两个信息想到使用哈希表，其key用来存储岛屿的编号，value存储岛屿的面积。

计算岛屿面积使用695.岛屿的最大面积的方法。DFS搜索时直接将格点的值修改为岛屿编号，修改后的岛屿编号还可以兼具标记已访问的功能，这就需要将岛屿编号修改为非0且非1的值，这里岛屿编号使用2，3，4，……

为什么岛屿编号要是非0非1的值？

编号为0并不影响DFS计算面积，但是在使用哈希表时会出现歧义，key==0时表示的是0号岛屿的面积还是海洋的面积？这里在编写代码是容易产生困惑；另外在第二次遍历整张图修改岛屿时，如何区分是海洋格点还是0号岛屿呢？这个原因就直接导致了不能使用0作为岛屿编号

编号为1时同理，在DFS搜索时就会遇到问题，对当前点标记为已访问时，如果标记成1（1号岛屿），那下次从其他陆地进入这个格点，如何判断这里是未访问的陆地（原本就是1）还是已经访问过的1号岛屿呢？所以岛屿编号既不能是0，也不能是1

计算得到所有岛屿的面积之后，再次遍历整图，判断每个海洋格点的周围是否有陆地格点，如有就根据陆地格点的编号到哈希表中查询其岛屿面积，将这个点周围的所有岛屿面积加和后再加上这个点本身的面积1，就得到了当前海洋格点变成陆地后的岛屿面积。维护一个最大面积，遍历结束后，得到最终的最大面积。

实现细节

DFS函数

计算面积使用DFS递归函数，修改自695.岛屿的最大面积的DFS函数，标记已访问时将格点内容标记为传入的参数label，表示岛屿编号，同一片岛屿使用相同的岛屿编号标记。

在判断递归结束条件时，进入海洋格点grid[i][j] == 0或者已被标记为访问过的格点grid[i][j] >= 2的判断条件合并为grid[i][j] != 1。

主函数

主函数首先完成岛屿面积的计算，遍历全图未被访问过的陆地格点grid[i][j] == 1，使用DFS计算面积并标记为编号label，每标记完一片岛屿后更新label的值，将计算得到的岛屿面积保存在哈希表unordered_map<int, int> grid_map中，哈希表的key为岛屿编号，value为岛屿面积。

此处需要注意，在计算面积时就要开始维护最终的最大面积结果result，因为输入中可能存在不需要变海洋为陆地的情况，例如输入样例3中所有格点都是陆地，没有海洋格点可以修改，此时获得的最大面积就是最后输出的最大面积。

接下来需要遍历全图的海洋格点，计算这个格点和周围相连的岛屿的面积，使用area记录，初始值为当前格点自己的面积1。

此处需要注意，有的海洋格点可能会与同一片岛屿有大于一条临边，如样例2的情况，海洋格点的上侧和左侧都是编号为2的岛屿，这种情况不要重复计算同一片岛屿面积。这里使用一个集合unordered_set<int> used_label保存已经累加岛屿面积的岛屿编号，在累加面积时先判断当前岛屿是否已经加过了。

代码

由于一直以来不习惯用四次循环+方向数组来对当前格点周围的四个点搜索，在最后检查海洋格点周围四个格点是否有陆地时，写出了vector<int> labels处极其丑陋的代码，十分影响可读性，但是不想改了。

labels的作用是经过越界检查后取出当前格点(i, j)四周的格点的值，用于在循环中判断当前位置四周是否是陆地lb > 1，如果是陆地就使用lb去查哈希表得到岛屿面积
如果当前格点是边界点，越界检查时会在labels中对应越界的位置存入-1，在循环中判断是否是陆地lb > 1会直接忽略。

class Solution {
public:
    int dfs(vector<vector<int>>& grid, int label, int i, int j) {
        int m = grid.size();
        int n = grid[0].size();
        // 岛屿 -> 边界之外，不产生面积
        if(i < 0 || j < 0 || i >= m || j >= n) return 0;
        // 进入海洋==0或者已经访问过>=2，不产生面积
        if(grid[i][j] != 1) return 0;
        // 将当前点标记为已访问
        grid[i][j] = label;
        // 向四周搜索，返回自身的面积1+四周的面积
        return (1 + dfs(grid, label, i - 1, j) + dfs(grid, label, i + 1, j) + dfs(grid, label, i, j - 1) +
                dfs(grid, label, i, j + 1));
    }
    int largestIsland(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int result = 0;
        // 岛屿编号
        int label = 2;
        // key 编号 value 面积
        unordered_map<int, int> grid_map;
        // 计算修改前的所有岛屿面积并完成编号
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1) {
                    grid_map[label] = dfs(grid, label, i, j);
                    // 可能存在不需要修改的情况，如样例3，此时也需要保留最大面积
                    result = max(grid_map[label], result);
                    label++;
                }
            }
        }
        // 遍历所有海洋，检查其四周是否有岛屿
        // 如果有则计算总面积并更新面积最大值
        int area = 1;
        // 同一编号的岛屿面积只能加一次（对应样例2）
        unordered_set<int> used_label;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] != 0) continue;
                // 当前点是海洋，area表示当前点连接的岛屿面积，初始为自身的面积1
                area = 1;
                used_label.clear();
                // 看四周是否有岛屿，有则加上他们的面积
                vector<int> labels{i + 1 < m ? grid[i + 1][j] : -1, i - 1 >= 0 ? grid[i - 1][j] : -1,
                                   j + 1 < n ? grid[i][j + 1] : -1, j - 1 >= 0 ? grid[i][j - 1] : -1};
                for(int lb : labels) {
                    if(lb > 1 && !used_label.count(lb)) {
                        area += grid_map[lb];
                        used_label.insert(lb);
                    }
                }
                // 更新最大面积
                result = max(area, result);
            }
        }
        return result;
    }
};

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。