130 Surrounded Regions

130. Surrounded Regions

1. Question

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

2. Implementation

(1) Union Find

思路:

(1) 用Union Find的方法，将 n * m作为一个特殊的parent id，表示所有与边连接的component的root

(2) 对于board上所有"O"，如果它在边上，则与 n * m的parent id union,否则将其四周的'O‘, 与其union

(3)

class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }

        int m = board.length, n = board[0].length;
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        UnionFind uf = new UnionFind(n * m + 1);

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'X') continue;

                if (i == 0 || i == m - 1 || j == 0 ||j == n - 1) {
                    uf.union(i * n + j, n * m);
                }
                else {
                    for (int[] direction : directions) {
                        int nextRow = i + direction[0];
                        int nextCol = j + direction[1];

                        if (board[nextRow][nextCol] == 'O') {
                            uf.union(nextRow * n + nextCol, i * n + j);
                        }
                    }
                }
            }
        }

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

    class UnionFind {
        int[] parents;
        int[] size;

        public UnionFind(int n) {
            parents = new int[n];
            size = new int[n];

            for (int i = 0; i < n; i++) {
                parents[i] = i;
                size[i] = 1;
            }
        }

        public int find(int id) {
            while (id != parents[id]) {
                id = parents[id];
            }
            return id;
        }

        public boolean isConnected(int i, int j) {
            return find(i) == find(j);
        }

        public void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);

            if (rootI == rootJ) return;

            if (size[rootI] < size[rootJ]) {
                parents[rootI] = rootJ;
                size[rootJ] += size[rootI];
            }
            else {
                parents[rootJ] = rootI;
                size[rootI] += size[rootJ];
            }
        }
    }
}

3. Time & Space Complexity

BFS: 时间复杂度O(mn), union-find中的函数时间复杂度接近常数, 空间复杂度O(mn), m和n分别为board的行数和列数