• y总题解（DFS）

  • 此题属于flood fill类型。 相似题目：ACWing题库 中 搜 flood fill。

• nettee（DFS），力扣官方（DFS 和 BFS），K神（DFS 和 BFS）。在 LeetCode 中，「岛屿问题」是一个系列问题，岛屿类问题的通用解法、DFS 遍历框架。

  • L200. 岛屿数量 （Easy）
  • 463. 岛屿的周长 （Easy）
  • 695. 岛屿的最大面积 （Medium）
  • 827. 最大人工岛 （Hard）

题目

200. 岛屿数量

思路

1. DFS: 时间 O(mn), 递归栈空间 O(mn)

• y总题解（DFS），nettee（DFS），力扣官方（DFS 和 BFS），K神（DFS 和 BFS）

// DFS: 时间 O(mn), 空间 O(mn)
class Solution {
public:
    vector<vector<char>> g; // 全局变量 就不用 dfs 里面作为 参数传进去了. 注意存的是char型
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; // 4 个方向: 左-上-右-下

    int numIslands(vector<vector<char>>& grid) {
        g = grid;
        int cnt = 0;
        for (int i = 0; i < g.size(); i ++ )
            for (int j = 0; j < g[i].size(); j ++ )
                if (g[i][j] == '1') { // 注意: 这里是char型 '1', 不是 int型 1
                    dfs(i, j);
                    cnt ++ ;
                }
        return cnt;
    }

    void dfs(int x, int y) { // 返回类型为 void
        g[x][y] = '2'; // 这里 可以 标记为 除 char型 '1' 之外的任何 标记

        for (int i = 0; i < 4; i ++ ) { // 遍历 4 个方向: 左-上-右-下
            int a = x + dx[i], b = y + dy[i]; // (a, b) 是 (x, y)点的 左-上-右-下 点的坐标

            // 注意 是 g[a].size() 不是 g[i].size(), i 只是 dx数组 和 dy数组 的 索引下表
            if (a >= 0 && a < g.size() && b >= 0 && b < g[a].size() && g[a][b] == '1')
                dfs(a, b);
        }
    }
};

• 如果 想 用 m = g.size(); n = g[0].size() 即 用 m, n 取代代码 中 用到 .size() 的地方，需 定义 m, n两个全局变量，注意定义全局变量时 只能是 声明，不能初始化赋值，只能 在 int numIslands() 函数里 才能初始化赋值。

class Solution {
public:
    vector<vector<char>> g; // 在 numIslands() 里才能初始化赋值
    // int m = g.size(), n = g[0].size(); // 在这写 m, n 会被初始化为 0 
    int m, n; // m 行数, n 列数
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; // 左-上-右-下

    int numIslands(vector<vector<char>>& grid) {
        g = grid;
        m = g.size(), n = g[0].size(); // 在这 才能 给 m, n 赋值
        int cnt = 0;

        for (int i = 0; i < m; i ++ )
            for (int j = 0; j < n; j ++ )
                if (g[i][j] == '1') {
                    dfs(i, j);
                    cnt ++ ;
                }
        return cnt;
    }

    void dfs(int x, int y) {
        g[x][y] = '0';

        for (int i = 0; i < 4; i ++ ) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < m && b >= 0 && b < n && g[a][b] == '1')
                dfs(a, b);
        }
    }
};

2. BFS：时间 O(mn), 空间 O(min(m, n))

• 力扣官方（DFS 和 BFS），K神（DFS 和 BFS）

// bfs: 时间 O(mn), 空间 O(min(m, n))
class Solution {
public:
    int numIslands(vector<vector<char>>& g) {
        int m = g.size(), n = g[0].size();

        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; // 左-上-右-下

        int cnt = 0;
        for (int i = 0; i < m; i ++ )
            for (int j = 0; j < n; j ++ )
                if (g[i][j] == '1') {
                    cnt ++ ;

                    // ----------------  bfs  ----------------
                    g[i][j] = '2';

                    queue<pair<int, int>>q;
                    q.push({i, j});

                    while (!q.empty()) {
                        auto t = q.front(); q.pop();
                        int x = t.first, y = t.second;

                        for (int k = 0; k < 4; k ++ ) {
                            int a = x + dx[k], b = y + dy[k];
                            if (a >= 0 && a < g.size() && b >= 0 && b <g[a].size() && g[a][b] == '1') {
                                q.push({a, b});
                                g[a][b] = '2'; // 这里是 '=', 一开始手残打成 "==", leetcode报超时
                            }
                        }
                    }
                    // ----------------  bfs  ----------------
                }
        return cnt;
    }
};

• 将 bfs部分单独拿出来：

// bfs: 时间 O(mn), 空间 O(min(m, n))
class Solution {
public:
    vector<vector<char>> g;

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; // 左-上-右-下

    int numIslands(vector<vector<char>>& grid) {
        g = grid;

        int cnt = 0;
        for (int i = 0; i < g.size(); i ++ )
            for (int j = 0; j < g[0].size(); j ++ )
                if (g[i][j] == '1') {
                    cnt ++ ;
                    bfs(i, j);
                }
        return cnt;
    }

    void bfs(int i, int j) {
        g[i][j] = '2';

        queue<pair<int, int>>q;
        q.push({i, j});

        while (!q.empty()) {
            auto t = q.front(); q.pop();
            int x = t.first, y = t.second;

            for (int k = 0; k < 4; k ++ ) {
                int a = x + dx[k], b = y + dy[k];
                if (a >= 0 && a < g.size() && b >= 0 && b <g[a].size() && g[a][b] == '1') {
                    q.push({a, b});
                    g[a][b] = '2'; // 这里是 '=', 一开始手残打成 "==", leetcode报超时
                }
            }
        }
    }
};