Leetcode-130. 被围绕的区域

130. 被围绕的区域
给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。

找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

示例:

X X X X
X O O X
X X O X
X O X X
运行你的函数后，矩阵变为：

X X X X
X X X X
X X X X
X O X X
解释:

被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
运行结果

解题思路
利用并查集的思想
将所有边缘上的O的父亲置为虚拟节点dimon
然后遍历其他的O，如果将其与其四周的O连通----使得与边缘的O相连的O的父亲也是dimon
这样再次遍历，只要父亲不是虚拟节点的O均置为X
java代码

class Solution {
    public void solve(char[][] board) {
        int m=board.length;
        if(m == 0) return;
        int n=board[0].length;
        UF uf=new UF(m*n+1);
        int domin=m*n;
        //左右边界的0和虚拟节点合并
        for(int i=0;i<m;i++){
            if(board[i][0]=='O'){
                uf.union(i*n,domin);
            }
            if(board[i][n-1]=='O'){
                uf.union(i*n+n-1,domin);
            }
        }
        //上下边界的0和虚拟节点合并
        for(int i=0;i<n;i++){
            if(board[0][i]=='O'){
                uf.union(i,domin);
            }
            if(board[m-1][i]=='O'){
                uf.union(n*(m-1)+i,domin);
            }
        }
        // 方向数组 d 是上下左右搜索的常用手法
        int[][] d = new int[][]{{1,0}, {0,1}, {0,-1}, {-1,0}};
        for(int i=1;i<m-1;i++){
            for(int j=1;j<n-1;j++){
                if(board[i][j]=='O'){
                    //将其与四周的O连通
                    for(int k=0;k<4;k++){
                        int x=i+d[k][0];
                        int y=j+d[k][1];
                        if(board[x][y]=='O'){
                            uf.union(x*n+y,i*n+j);
                        }
                    }
                }
            }
        }
        // 所有不和 dummy 连通的 O，都要被替换
        for(int i=1;i<m-1;i++){
            for(int j=1;j<n-1;j++){
                if(board[i][j]=='O' &&!uf.getconnected(i*n+j,domin)){
                    board[i][j]='X';
                }
            }
        }
    }
    class UF{
        private int[] parent;
        private int[] size;
        private int count;

        public UF(int n){
            parent=new int[n];
            size=new int[n];
            count=n;
            for(int i=0;i<n;i++){
                parent[i]=i;
                size[i]=1;
            }
        }

        public void union(int a,int b){
            int roota=find(a);
            int rootb=find(b);
            if(roota == rootb) return;
            if(size[roota]>size[rootb]){
                parent[rootb]=roota;
                size[roota]+=size[rootb];
            }
            else{
                parent[roota]=rootb;
                size[rootb]+=size[roota];
            }
        }

        public int find(int x){
            while(parent[x] != x){
                parent[x]=parent[parent[x]];
                x=parent[x];
            }
            return x;
        }

        public boolean getconnected(int a,int b){
            int roota=find(a);
            int rootb=find(b);
            return roota==rootb;
        }

        public int getcount(){
            return count;
        }
    }
}