Surrounded Regions

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Subscribe to see which companies asked this question

利用并查集，如果一个pos处为'O'，则将这个pos四个方向的位置上为'O'的parent均置为此pos的parent，需要注意的是如果这个点在边界，我们假想了一个点，所有的边界点的parent均是假想的这个点

class UnionF{
private:
    int *parent;
    int *rank;
    int size;
public:
    UnionF(int N){
        parent = new int[N];
        rank = new int[N];
        size = N;
        for(int i = 0; i < N; i++){
            parent[i] = i;
            rank[i] = 0;
        }
    }

    ~UnionF(){
        delete []parent;
        delete []rank;
    }

    int find(int x){
        if(x == parent[x]){
            return x;
        }else{
            return parent[x] = find(parent[x]);
        }
    }

    bool isConnected(int x, int y){
        return find(x) == find(y);
    }

    void unite(int x, int y){
        x = find(x);
        y = find(y);

        if(x == y)    return;

        if(rank[x] < rank[y]){
            parent[x] = y;
        }else{
            parent[y] = x;
            if(rank[x] == rank[y]){
                rank[x]++;
            }
        }
    }
};

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int n = board.size();

        if(n == 0)    return;

        int m = board[0].size();

        UnionF uf = UnionF(n*m + 1);

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                //boundary
                if(board[i][j] == 'O'&&i == 0 || i == n - 1 || j == 0 || j == m - 1){
                    uf.unite(i * m + j, n*m);
                }else if(board[i][j] == 'O'){
                    //four direction
                    if(board[i - 1][j] == 'O')
                        uf.unite(i*m + j, (i - 1)*m + j);
                    if(board[i + 1][j] == 'O')
                        uf.unite(i*m + j, (i + 1)*m + j);
                    if(board[i][j - 1] == 'O')
                        uf.unite(i*m + j, i*m +(j - 1));
                    if(board[i][j + 1] == 'O')
                        uf.unite(i*m + j, i*m + (j + 1));
                }
            }
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(!uf.isConnected(i*m + j, n*m))
                    board[i][j] = 'X';
            }
        }
    }
};