130. 被圍繞的區域

洪水填充

給定一個由 O, X組成的矩陣，把所有「被圍繞的區域」改為 X，
被圍繞的區域，也可以視為沒有跟邊緣相鄰的區域，對於上圖在中間的三個O來說，它們彼此相連，但沒有一個跟邊緣相鄰，因此是「被圍繞的區域」，修改為X。
使用洪水填充去做，需要分為幾個階段\

1. 遍歷所有「邊緣」節點，若邊緣的節點是O，則往四方向擴散。

• 此時因為擴散而被走訪到的節點都是O，並且都跟邊緣相連，

因此，在最後的答案裡，這時被走訪到的節點要保持原樣。

2. 遍歷所有節點，若節點是O，往四方向擴散。

• 在上一步中，我們走訪過的節點應該要被保留，所以在第二次擴散時，如果節點已經被走訪過，就表示它應該要被保留，否則應該改為X。

更細節的流程，在程式碼的註解當中有寫。

1. 洪水填充 使用變數分辨階段

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int n = board.size(), m = board[0].size();
        vector<vector<bool>> visited(n,  vector<bool>(m, false));        
        const int dir[5] = {-1, 0, 1, 0, -1};
        bool checkOnly = true; // 在遍歷邊緣時，被走訪的 O 不應該被改為 X

        auto dfs = [&](this auto&&dfs, int i, int j) {
            if(i < 0 || i >= n || j < 0 || j >= m || visited[i][j] || board[i][j] == 'X') {
                return;
            }
            if(!checkOnly) {
                board[i][j] = 'X';
            }
            visited[i][j] = true; // 標記為已走訪
            for(int k = 0; k < 4; k++) {
                dfs(i + dir[k], j + dir[k + 1]); // 往四個方向擴散
            }
        };

        for(int i = 0; i < n; i++) {
            dfs(i, 0);
            dfs(i, m - 1);
        }
        for(int j = 0; j < m; j++) {
            dfs(0, j);
            dfs(n - 1, j);
        }
        
        checkOnly = false; // 遍歷好邊緣，此時跟邊緣相接的 O 都被標記為已走訪，不會被誤標為 X 
        for(int i = 1; i < n; i++) {
            for(int j = 1; j < m; j++) {
                dfs(i, j);
            }
        }
    }
};

2. 洪水填充 使用佔位符分辨

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int n = board.size(), m = board[0].size();
        const int dir[5] = {-1, 0, 1, 0, -1};

        auto dfs = [&](this auto&&dfs, int i, int j, char replace) {
            if(i < 0 || i >= n || j < 0 || j >= m || board[i][j] == 'X' || board[i][j] == '#') {
                return;
            }
            board[i][j] = replace;
            for(int k = 0; k < 4; k++) {
                dfs(i + dir[k], j + dir[k + 1], replace);
            }
        };

        for(int i = 0; i < n; i++) { // 遍歷邊緣時，把走訪到的 O 改成 #, # 代表跟邊緣相連的 O。
            dfs(i, 0, '#');
            dfs(i, m - 1, '#');
        }
        for(int j = 0; j < m; j++) {
            dfs(0, j, '#');
            dfs(n - 1, j, '#');
        }
        for(int i = 1; i < n; i++) { // 遍歷所有節點時，把走訪的 O 改成 X 
            for(int j = 1; j < m; j++) {
                dfs(i, j, 'X');
            }
        }
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(board[i][j] == '#') { // 最後，把 # 改回 O
                    board[i][j] = 'O';
                }
            }
        }
    }
};

並查集

除了洪水填充之外，也可以用用並查集做，但比較麻煩。
要有一個「虛擬節點」boardID用來代表邊緣，這裡用 $n\times{m}$ 代表。

1. 先把所有在邊緣上的 O 節點都跟邊緣節點相連，後面查找時，假如發現根節點是boardID，表示這個節點跟邊緣相連。
2. 在邊緣合併完成之後，遍歷所有節點，並跟自己周邊的節點合併到相同集合。
3. 最後，遍歷所有節點，查找每個節點的根節點是不是boardID，用來判斷是否被圍繞。

需要注意的是，在合併節點時，應該從編號小的節點合併到大的節點，否則boardID可能會不再是根節點，判斷就會出錯。

程式碼

class Solution {
private:
    static const int MX = 40005;
    int parent[MX];
    int find(int x) {
        if(x != parent[x]) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    void build(int n) {
        iota(parent, parent + n + 1, 0);
    }
    bool isSameSet(int x, int y) {
        return find(x) == find(y);
    }
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        parent[min(rootX, rootY)] = max(rootX, rootY);
    }

public:
    void solve(vector<vector<char>>& board) {
        int n = board.size(), m = board[0].size();
        int boardID = n * m;
        build(n * m);

        auto getIndex = [&](int x, int y) {
            return x * m + y;
        };

        // 將邊緣的 O 節點跟 boardID 合併到相同集合。
        for(int i = 0; i < n; i++) {
            if(board[i][0] == 'O') unite(getIndex(i, 0), boardID);
            if(board[i][m - 1] == 'O') unite(getIndex(i, m - 1), boardID);
        }
        for(int j = 0; j < m; j++) {
            if(board[0][j] == 'O') unite(getIndex(0, j), boardID);
            if(board[n - 1][j] == 'O') unite(getIndex(n - 1, j), boardID);
        }
        
        // 遍歷所有節點，把 O 跟附近的 O 合併到相同集合。
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(board[i][j] == 'O') {
                    int index = getIndex(i, j);
                    if(i >= 1 && board[i - 1][j] == 'O') {
                        unite(getIndex(i - 1, j), index);
                    }
                    if(j >= 1 && board[i][j - 1] == 'O') {
                        unite(getIndex(i, j - 1), index);
                    }
                }
            }
        }
        
        // O 所屬的集合如果不屬於邊緣，表示它被圍繞，修改為 X 
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(board[i][j] == 'O' && find(getIndex(i, j)) != boardID) {
                    board[i][j] = 'X';
                }
            }
        }
    }
};

複雜度分析

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