算法

岛屿数量

loser

31 Aug 2026 • 4 min read

给定一个由字符 '1' 和 '0' 组成的二维网格，其中 '1' 代表陆地，'0' 代表水。水平或竖直方向相邻的陆地属于同一座岛屿，求网格中的岛屿数量。

示例

示例 1

输入：grid = [['1','1','1','1','0'], ['1','1','0','1','0'], ['1','1','0','0','0'], ['0','0','0','0','0']]

输出：1

示例 2

输入：grid = [['1','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1']]

输出：3

提示

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'

代码

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int islandCount = 0;
        int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        for (int row = 0; row < m; ++row) {
            for (int col = 0; col < n; ++col) {
                if (grid[row][col] == '0') {
                    continue;
                }

                ++islandCount;
                stack<pair<int, int>> cells;
                cells.push({row, col});
                grid[row][col] = '0';

                while (!cells.empty()) {
                    auto [currentRow, currentCol] = cells.top();
                    cells.pop();

                    for (const auto& direction : directions) {
                        int nextRow = currentRow + direction[0];
                        int nextCol = currentCol + direction[1];

                        if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n) {
                            continue;
                        }
                        if (grid[nextRow][nextCol] == '0') {
                            continue;
                        }

                        grid[nextRow][nextCol] = '0';
                        cells.push({nextRow, nextCol});
                    }
                }
            }
        }

        return islandCount;
    }
};

核心思路

将问题转化为连通块计数

一座岛屿本质上是由四个方向相邻的陆地组成的连通块。因此，可以从左到右、从上到下扫描整个网格：

遇到水域时直接跳过。
遇到尚未访问的陆地时，说明发现了一座新岛屿，答案加一。
以该陆地为起点进行 DFS，将所有与它四方向连通的陆地全部访问。

这样，后续扫描就不会再次统计同一座岛屿。

原地标记访问状态

代码直接将访问过的陆地 '1' 改成水域 '0'，不需要额外的 visited 数组。

标记时机是在陆地入栈时，而不是出栈时。这样可以避免同一块陆地被多个相邻节点重复加入栈中。

四方向扩展

对于当前坐标 (row, col)，只检查：

(row - 1, col)：上
(row + 1, col)：下
(row, col - 1)：左
(row, col + 1)：右

不检查对角线方向，符合题目对岛屿连接方式的定义。

正确性证明

每次 DFS 只访问一座岛屿

DFS 从一个未访问的陆地开始，并且只沿上、下、左、右四个方向扩展到陆地。因此，它访问到的所有位置都与起点属于同一个四方向连通块，不会跨越水域到达另一座岛屿。

每座岛屿都会被统计一次

扫描网格时，一座岛屿中最先遇到的陆地会触发一次 DFS，并使岛屿数量加一。该 DFS 会把整座岛屿的所有陆地标记为 '0'，所以同一座岛屿中的其他陆地不会再次触发计数。

不同岛屿之间至少隔着水域，DFS 无法从一座岛屿扩展到另一座岛屿，因此每座岛屿都恰好触发一次计数。

综上，算法返回的 islandCount 就是网格中的岛屿总数。

示例分析

以示例 2 为例，扫描过程如下：

扫描到左上角陆地时，DFS 访问左上区域，统计第 1 座岛屿。
扫描到第三行中间的陆地时，它与前一座岛屿不相邻，统计第 2 座岛屿。
扫描到右下区域的陆地时，统计第 3 座岛屿。

因此最终返回 3。

复杂度分析

时间复杂度：O(mn)。每个网格位置最多被扫描并标记一次。
空间复杂度：O(mn)。最坏情况下，栈中可能同时保存 O(mn) 个网格位置；除此之外只使用常数级额外空间。

边界情况

网格中全部是水：没有位置触发 DFS，返回 0。
网格中只有一座岛屿：第一次 DFS 会访问整座岛屿，返回 1。
岛屿位于边界：通过坐标范围判断避免访问越界位置。
只有一行或一列：仍然只按四方向检查有效相邻位置，算法同样成立。