岛屿数量

GitHub跳转原题关系图返回列表

遇到未访问陆地就 DFS 淹没整块，计数加一。

OJ: leetcodecn

题目 ID: number-of-islands

难度:普及+/提高

标签:DFSBFS网格cpppython

日期: 2026-07-29 13:10

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

网格中 ‘1’ 为陆地，找连通块数量。

思路

扫描网格，遇到 ‘1’ 就 DFS/BFS 将整块淹没并计数。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int numIslands(vector<vector<char>> &grid) {
        int m = grid.size(), n = grid[0].size(), ans = 0;
        function<void(int, int)> dfs = [&](int i, int j) {
            if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0')
                return;
            // 原地改成水，既标记访问状态，也避免同一陆地被重复搜索。
            grid[i][j] = '0';
            dfs(i - 1, j);
            dfs(i + 1, j);
            dfs(i, j - 1);
            dfs(i, j + 1);
        };
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == '1') {
                    ans++;
                    dfs(i, j);
                }
        return ans;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, n;
    cin >> m >> n;
    vector<vector<char>> g(m, vector<char>(n));
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> g[i][j];
    cout << Solution().numIslands(g) << '\n';
    return 0;
}
python
#!/usr/bin/env python3
from typing import List


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])

        def dfs(i, j):
            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == "0":
                return
            grid[i][j] = "0"
            for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                dfs(i + di, j + dj)

        ans = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    ans += 1
                    dfs(i, j)
        return ans


def main():
    m, n = map(int, input().split())
    g = [input().split() for _ in range(m)]
    print(Solution().numIslands(g))


if __name__ == "__main__":
    main()

复杂度

时间 O(mn)，空间 O(mn) 递归栈。

总结

淹没法是连通块计数的标准 DFS 做法。