200. 岛屿数量

难度：🟡 Medium | 标签：图论、DFS、BFS、并查集 | 状态：⬜ LeetCode 链接

思路

扫描每个格子，遇到 ‘1’ 就 DFS 染色（改成 ‘0’），整片陆地变零后岛数 +1。

代码

class Solution {
    int R, C;
    void dfs(vector<vector<char>>& g, int i, int j) {
        if (i < 0 || j < 0 || i >= R || j >= C || g[i][j] != '1') return;
        g[i][j] = '0';
        dfs(g, i + 1, j); dfs(g, i - 1, j);
        dfs(g, i, j + 1); dfs(g, i, j - 1);
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        R = grid.size(); C = grid[0].size();
        int cnt = 0;
        for (int i = 0; i < R; ++i)
            for (int j = 0; j < C; ++j)
                if (grid[i][j] == '1') { ++cnt; dfs(grid, i, j); }
        return cnt;
    }
};

复杂度

• 时间 O(R · C)，空间 O(R · C)（递归栈最坏）

易错 / 回顾

• DFS 不要漏判 g[i][j] != '1'（包括边界外、已染色、海洋）
• 染色后不要复原（与回溯类题不同）
• 大网格用 BFS 防爆栈