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

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

Have you met this question in a real interview?

Yes

Example

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

After capture all regions surrounded by'X', the board should be:

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

Union Find

思考顺序是

1. 用union find的查询元素是否在同一集合的功能
2. 问题转化为，不在边界的‘O'是否和在边界的'O'在同一集合内？
3. 把边界的点联通入同一集合，在遍历每一个不在边界的’O‘点并与其周围的’O‘点联通
4. 最后遍历把不在周边集合内的’O'变成‘X'即可
5. 时间复杂度O(mnlog(m*n)), 空间复杂度 O(mn)

class UnionFind {
    private int[] father;
    public UnionFind(int n) {
        father = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            father[i] = i;
        }
    }

    private int find(int a) {
        if (father[a] == a) {
            return a;
        }
        return father[a] = find(father[a]);
    }

    public void union(int a, int b) {
        int root_a = find(a);
        int root_b = find(b);

        if (root_a != root_b) {
            father[root_a] = root_b;
        }
    }

    public boolean isConnected(int a, int b) {
        return find(a) == find(b);
    }
}

public class Solution {
    /*
     * @param board: board a 2D board containing 'X' and 'O'
     * @return: nothing
     */
    public void surroundedRegions(char[][] board) {
        // write your code here
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) {
            return;
        }

        int n = board.length;
        int m = board[0].length;
        UnionFind uf = new UnionFind(n * m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'O') {

                    int index = i * m + j;
                    for (int k = 0; k < dx.length; k++) {
                        int new_i = i + dx[k];
                        int new_j = j + dy[k];
                        int new_index = new_i * m + new_j;
                        if (new_i >= 0 && new_j >= 0 && new_i < n && new_j < m && board[new_i][new_j] == 'O') {
                            uf.union(index, new_index);
                        }
                    }
                    if (i == 0 || j == 0 || i == n - 1 || j == m - 1) {
                        uf.union(i * m + j, n * m);
                    }
                }
            }
        }

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