200. Number of Islands

題目網址：https://leetcode.cn/problems/number-of-islands/

題意：給一 m x n 的二維矩陣 grid, 其中 '1' 代表陸地, 而 '0' 代表水, 返回島嶼的個數。

每座島嶼只能由水平 or 垂直方向的相鄰陸地連接而成。

Solution 1：

想法：利用 DFS, 若 grid[row][col] == 1, 則以其為起始 node 開始進行 DFS。在 DFS 的過程中. 每個搜索到的 1 都會被重新標記為 0, 最後整個地圖都會變成水

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size(), n = grid[0].size();

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

private:
    int m, n;
    vector<pair<int, int>> dirs = {
        {0, 1}, {0, -1},
        {1, 0}, {-1, 0}
    };

    void dfs(vector<vector<char>>& grid, int i, int j){
        if (outOfBound(i, j) || grid[i][j] == '0') {
            return;
        }

        grid[i][j] = '0'; // 表示已拜訪過

        for (const auto& [dirY, dirX] : dirs) {
            dfs(grid, i + dirY, j + dirX);
        }
    }

    bool outOfBound(int i, int j){
        if (i < 0 || i == m || j < 0 || j == n) {
            return true;
        }
        return false;
    }
};

• time：$O(m \cdot n)$ ➔ for loop
• space：$O(m \cdot n)$ ➔ 取決於遞迴深度, 最大遞迴深度為 $mn$（worse case：全部都是陸地）

Solution 2：

想法：利用 BFS, 概念類似 Solution 1, 拜訪後一樣要設為 0。若在 q.pop() 下面放 grid[row][col] = '0', 而不是在將 {r, c} push 到 q 時將 grid[r][c] 設為 0, 這樣會使 node 被重複拜訪, 導致 TLE

e.g. grid = [[1, 1], [1, 1]]

• 若是在 q.pop() 下面放 grid[row][col] = '0', 則 grid[1][1] 會被 grid[0][1] 和 grid[1][0] 重複拜訪（因為 grid[1][1] 在下一輪的 q.pop() 後才被設為 0）

  

• 若是在將 {r, c} push 到 q 時將 grid[r][c] 設為 0, 則 grid[1][1] 只會被 grid[1][0] 拜訪。因為在 grid[0][1] 的 for loop 中 if (grid[1][1] == '1') 不會成立, 因為 grid[1][1] 已經在 grid[1][0] 的 for loop 中被設成 0

typedef pair<int, int> pii;

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size(), n = grid[0].size();

        int res = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1') {
                    bfs(grid, i, j);
                    ++res;
                }
            }
        }
        return res;
    }

private:
    int m, n;
    queue<pii> q;
    vector<pii> dirs = {
        {0, 1}, {0, -1},
        {1, 0}, {-1, 0}
    };

    void bfs(vector<vector<char>>& grid, const int i, const int j){
        q.emplace(pii{i, j});

        while (!q.empty()) {
            for (int k = q.size(); k > 0; --k) {
                const auto [row, col] = q.front();
                q.pop();

                for (const auto& [dirY, dirX] : dirs) {
                    const int r = row + dirY, c = col + dirX;
                    if (!outOfBound(r, c) && grid[r][c] == '1') {
                        grid[r][c] = '0';
                        q.emplace(pii{r, c});
                    }
                }
            }
        }
    }

    bool outOfBound(const int i, const int j){
        if (i < 0 || i == m || j < 0 || j == n) {
            return true;
        }
        return false;
    }
};

• time：$O(m \cdot n)$ ➔ for loop
• space：$O(min(m, n))$ ➔ worse case：全部都是陸地, 則 q 的長度最多為 min(m, n), 也就是圖中線的最大長度

Solution 3：

想法：利用 Union Find + Path Compression, 將所有的連在一起的 1 的位置歸到一個 root, 最後有多少個 root 就有多少個島嶼。值得注意的是, 與 DFS 或者 BFS 的方法不同的是, 不需要搜索四個方向, 只需要看兩個方向（右、下）即可

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size(), n = grid[0].size();
        parents.resize(m * n, 0);
        ranks.resize(m * n, 1);

        // 初始化 parents, 每個 node 指向自己
        for (int i = 0; i < m * n; ++i) {
            parents[i] = i;
        }

        int res = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1') {
                    ++res;
                    for (const auto& [dirY, dirX] : dirs) {
                        const int r = i + dirY, c = j + dirX;

                        // (i, j) 和 (r, c) 做 union
                        if (!outOfBound(r, c) && grid[r][c] == '1') {
                            union_(i * n + j, r * n + c, res);
                        }
                    }
                }
            }
        }
        return res;
    }

private:
    int m, n;
    vector<int> parents, ranks;
    vector<pair<int, int>> dirs = {
        {0, 1}, {1, 0}
    };

    void union_(const int n1, const int n2, int& res){
        const int r1 = find(n1); // root of n1
        const int r2 = find(n2); // root of n2

        // 如果 n1, n2 是同個 set, 則不做任何事
        if (r1 == r2) {
            return;
        }

        // n1, n2 是不同 set, 則兩個 set 合併成一個 set
        // 深度低的 tree root 把深度高的 tree root 作為 parent
        if (ranks[r1] > ranks[r2]) {
            parents[r2] = r1;
        } else if (ranks[r1] < ranks[r2]) {
            parents[r1] = r2;
        } else { // 若深度一樣, 可以任意選擇一個 root 作為 parent
            parents[r2] = r1;
            ++ranks[r1]; // 作為 parent 的 node 之 rank 值會加一, 因為深度變了
        }
        --res; // 合併後, set 數 - 1
    }

    int find(int i){
        while (i != parents[i]) {
            parents[i] = parents[parents[i]]; // path compression
            i = parents[i];
        }
        return i;
    }

    bool outOfBound(const int i, const int j){
        if (i < 0 || i == m || j < 0 || j == n) {
            return true;
        }
        return false;
    }
};

• time：$O(m \cdot n)$ ➔ for loop
• space：$O(m \cdot n)$ ➔ parent, ranks