130. Surrounded Regions

问题：

给定一个m*n棋盘，由O和X填入。

将棋盘中被X包围的O转化成X。

说明：在四周边缘的O，以及和这些O相邻（上下左右相邻）的O，无法转化。其他的棋盘内部O皆可转化为X。

Example 1:
Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Explanation: Surrounded regions should not be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

Example 2:
Input: board = [["X"]]
Output: [["X"]]
 
Constraints:
m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] is 'X' or 'O'.

　　

解法：BFS, Disjoint Set（并查集）

解法一：BFS

queue：保存当前一层遍历中，遇到的O。（从四边缘开始，每相邻一层，为新的一层）

对当前格子：无法转化的对象：将board上标记为 $

若相邻为O 且 该格子没有访问过，则，q.push（{i, j}）

最后遍历board，若标记为$,则填入O，其他的O填入X。

代码参考：

class Solution {
public:
    bool isValid(int i, int j, int m, int n) {
        if(i<0 || j<0 || i>=m || j>=n) return false;
        return true;
    }
    void solve(vector<vector<char>>& board) {
        int m = board.size(), n = board[0].size();
        vector<vector<bool>> visited(m,vector<bool>(n,0));
        queue<vector<int>> q;
        vector<vector<int>> dir = {{1,0},{-1,0},{0,1},{0,-1}};
        for(int i=0; i<m; i++) {
            if(board[i][0] == 'O') {
                q.push({i, 0});
                visited[i][0] = 1;
            }
            if(board[i][n-1] == 'O') {
                q.push({i, n-1});
                visited[i][n-1] = 1;
            }
        }
        for(int j=0; j<n; j++) {
            if(board[0][j] == 'O') {
                q.push({0, j});
                visited[0][j] = 1;
            }
            if(board[m-1][j] == 'O') {
                q.push({m-1, j});
                visited[m-1][j] = 1;
            }
        }
        while(!q.empty()) {
            int sz = q.size();
            for(int k=0; k<sz; k++) {
                vector<int> cur = q.front();
                q.pop();
                board[cur[0]][cur[1]] = '$';
                for(vector<int> d:dir) {
                    int i = cur[0]+d[0], j = cur[1]+d[1];
                    if(isValid(i, j, m, n) && visited[i][j] != 1 && board[i][j] == 'O') {
                        q.push({i, j});
                        visited[i][j] = 1;
                    }
                }
            }
        }
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                if(board[i][j] == '$') board[i][j] = 'O';
                else if(board[i][j] == 'O') board[i][j] = 'X';
            }
        }
        return;
    }
};

解法二：Disjoint Set

将所有无法转化 X 的 O 连接到一起，标记到 dummy=m*n 这个值（不存在于数组坐标0～m*n-1）

首先，将四边缘上的 O 与 dummy 连接。

然后遍历所有坐标，若存在 O，将其与其四个方向上的节点相连。

这时有两种情况：

• 这个 O 最终连接上了 dummy：那么该节点无法转化为 X
• 这个 O 最终没有连接上 dummy：那么该节点需要转化为 X

最后再遍历一次所有坐标，对于 O 的节点

若没连接上 dummy，那么转化为 X

代码参考：

class Solution {
public:
    bool isValid(int i, int j, int m, int n) {
        if(i<0 || j<0 || i>=m || j>=n) return false;
        return true;
    }
    void solve(vector<vector<char>>& board) {
        int m = board.size(), n = board[0].size();
        vector<vector<int>> dir = {{1,0},{-1,0},{0,1},{0,-1}};
        DisjointSet ds(m*n+1);
        for(int i=0; i<m; i++) {
            if(board[i][0] == 'O') ds.merge(i*n+0, m*n);
            if(board[i][n-1] == 'O') ds.merge(i*n+(n-1), m*n);
        }
        for(int j=0; j<n; j++) {
            if(board[0][j] == 'O') ds.merge(0+j, m*n);
            if(board[m-1][j] == 'O') ds.merge((m-1)*n+j, m*n);
        }
        for(int i=1; i<m-1; i++) {
            for(int j=1; j<n-1; j++) {
                if(board[i][j] == 'O') {
                    for(vector<int> d:dir) {
                        int x = i+d[0], y = j+d[1];
                        if(board[x][y] == 'O') {
                            ds.merge(i*n+j, x*n+y);
                        }
                    }
                }
                
            }
        }
        for(int i=1; i<m-1; i++) {
            for(int j=1; j<n-1; j++) {
                if(board[i][j] == 'O' && !ds.isConnected(i*n+j, m*n)) {
                    board[i][j] = 'X';
                }
            }
        }
        return;
    }
};

Disjoint Set 类

class DisjointSet {
public:
    DisjointSet(int n):root(n,0),rank(n,0) {
        for(int i=0; i<n; i++) {
            root[i]=i;
        }
    }
    int find(int i) {
        if(root[i]!=i) {
            root[i] = find(root[i]);
        }
        return root[i];
    }
    void merge(int x, int y) {
        int x_root = find(x);
        int y_root = find(y);
        if(x_root == y_root) return ;
        if(rank[x_root]>rank[y_root]) {
            root[y_root] = x_root;
        } else if(rank[x_root]<rank[y_root]) {
            root[x_root] = y_root;
        } else {
            root[y_root] = x_root;
            rank[x_root] ++;
        }
        return ;
    }
    bool isConnected(int x, int y) {
        int x_root = find(x);
        int y_root = find(y);
        return x_root==y_root;
    }
private:
    vector<int> root;
    vector<int> rank;
};