200. 島嶼數量

給定一個二維陣列，裡面只包含 0, 1，分別代表海水跟陸地，
「一塊 1」就代表一個島嶼，問你有多少個島嶼。

並查集

使用並查集，為每一個位置給定編號，
如果一個陸地周邊有其他陸地，就把這些陸地合併到相同的集合當中。
在合併時，只需要看自己左邊的 1, 以及上面的 1，因為如果右邊跟下面有 1，到那時它會連接過來
除了並查集之外，還可以用dfs，把走過的地方標記為0代表已經走訪過，就不用創建額外空間。

class Solution {
private:
    static const int MX = 90001;
    int parent[MX];
    int setCnt;
    int find(int x) {
        if(x != parent[x]) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if(rootX != rootY) {
            parent[rootX] = rootY;
            setCnt--;
        }
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        
        auto getIndex = [&](int x, int y) -> int {
            return x * m + y;
        };

        // 並查集初始化
        setCnt = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(grid[i][j] == '1') { // 只留陸地的集合
                    int index = getIndex(i, j);
                    parent[index] = index;
                    setCnt++;
                }
            }
        }

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(grid[i][j] == '1') {
                    int index = getIndex(i, j);
                    if(i > 0 && grid[i - 1][j] == '1') {
                        unite(getIndex(i - 1, j), index);
                    }
                    if(j > 0 && grid[i][j - 1] == '1') {
                        unite(getIndex(i, j - 1), index);
                    }
                }
            }
        }
        return setCnt;
    }
};

洪水填充

洪水填充的整個流程很簡單：

1. 從滿足條件的節點開始往四周擴散，並把滿足條件的節點「填充」。
   • 這裡的填充，意思是把節點標記為走訪過，避免後續來回擴散。
2. 假如被擴散的的節點同樣滿足條件，那麼就再次擴散。

套用到這個題目就是：

1. 從陸地節點開始往四周擴散，並把陸地節點「填充」
2. 假如周圍同樣是陸地且沒有被走訪過，相鄰的陸地就再次擴散，

如此一來，當遇到一塊 $1$ 的其中一個位置時，整個島嶼的 $1$ 都會因為相鄰而被標記為走訪。整體複雜度 $O(nm)$ ，每個節點最多只會展開一次，並被上下左右嘗試訪問四次。

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        const int dir[5] = {-1, 0, 1, 0, -1}; // 四個方向。

        auto dfs = [&](this auto&&dfs, int i, int j) -> void {
            if(i < 0 || i >= n || j < 0 || j >= m || grid[i][j] == '0') { // 越界或走訪過，則遞迴終止。
                return;
            }
            grid[i][j] = '0'; // 標記為走訪過，這裡用 '0'
            for(int k = 0; k < 4; k++) { // 往四個方向填充
                int ni = i + dir[k];
                int nj = j + dir[k + 1];
                dfs(ni, nj);
            }
        };

        int res = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(grid[i][j] ==　'1') { // 把當前走訪到的陸地，以及周邊陸地一同標記為0
                    dfs(i, j); // 洪水填充
                    res++; // 島嶼數量增加
                }
            }
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(nm)$
• 空間複雜度：$O(nm)$