130. Surrounded Regions

problem descripition

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.

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
Explanation:

Surrounded regions shouldn’t 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.

algorithm thought

这个题目意思简单装换过来就是，如果一块圆区域如果连接到外面的话，那么这块圆就不变成X，否则都变为X。

这里可以用DFS做，从最外围的圆开始往中间遍历，碰到的圆都不变，其他的都变。

这里还可以用并查集做，由于想回顾并查集，所以这里我用这种方法解题。并查集是能快速找到一组组数据的数据结构，我们将外围区域定义一个节点，其他节点就是每个点自身。开始所有的节点的父节点都是自己。然后遍历数组，如果是最外层的圆，就将它和外围区域节点相连，如果是内部的圆，将它和它旁边的圆相连。最后再次遍历数组，如果圆连接到了外围节点，则保持不变，否则变为X

code

class Union_find{
public:
    explicit Union_find(int count):count(count){
        father=new int[count];
        rank=new int[count];
        for(int i=0;i<count-1;++i){
            father[i]=i;
            rank[i]=0;
        }
        rank[count-1]=100;
        father[count-1]=count-1;
    }
    virtual ~Union_find(){
        delete[] father;
        delete[] rank;
    }
    int getcount(){
        return count;
    }
    bool connected(int i,int j){
        return find(i)==find(j);
    }
    int find(int i){    //路径压缩
        if(i==father[i])
            return i;
        return father[i]=find(father[i]);
    }
    void connect(int i,int j){
        //cout<<i<<'-'<<j<<' ';
        int father_i=find(i);
        int father_j=find(j);
        //cout<<i<<'-'<<j<<' ';
        if(father_i==father_j){
            return;
        }else{
            if(rank[father_i]>rank[father_j]){
                father[father_j]=father_i;
                rank[father_i]++;
                //cout<<father_j<<'-'<<father_i<<' ';
            }else{
                father[father_i]=father_j;
                rank[father_j]++;
                //cout<<father_i<<'-'<<father_j<<' ';
            }
            //count--;
        }
    }
    void show(){
        for(int i=0;i<count;++i){
            cout<<father[i]<<' ';
        }
    }
private:
    int* father;    //父节点
    int* rank;  //节点的等级，带的子节点越多，等级越高，等级低的连在等级高的后面
    int count; //节点的数量
};

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if(board.size()==0||board[0].size()==0)
            return ;
        int row=board.size();
        int col=board[0].size();
        Union_find nf(row*col+1);
        for(int i=0;i<row;++i){
            for(int j=0;j<col;++j){
                if(board[i][j]=='O'){
                    if((i==0||j==0||i==row-1||j==col-1)){
                        nf.connect(i*col+j,row*col);
                    }else{
                        if(board[i+1][j]=='O')
                            nf.connect(i*col+j,(i+1)*col+j);
                        if(board[i][j+1]=='O')
                            nf.connect(i*col+j,i*col+j+1);
                        if(board[i][j-1]=='O')
                            nf.connect(i*col+j,i*col+j-1);
                        if(board[i-1][j]=='O')
                            nf.connect(i*col+j,(i-1)*col+j);
                    }
                }
            }
        }

       // nf.show();

        for(int i=0;i<row;++i){
            for(int j=0;j<col;++j){
                if(board[i][j]=='O'){
                    if(nf.find(i*col+j)!=row*col)
                        //cout<<i<<'-'<<j<<'-'<<nf.find(i*row+j)<<' ';
                        board[i][j]='X';
                }
            }
        }
    }
};

algorithm thoguht

首先构造并查集，在并查集有路径压缩时，插入和查找的时间都是O(1),最后时间复杂度O(n²)。然后遍历数组，时间复杂度O(n²),最后时间复杂度O(n²)