130. Surrounded Regions

https://leetcode.com/problems/surrounded-regions/description/

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.

Thoughts

由X和O组成的矩阵，将四周都被X围起来的O替换成X。UnionFind配合dummy node，把连在一起的结点像Number of Islands一样连起来，且把所有不被围着的（在边上的）和dummy node连起来。最后对每个'O'检查其是否和dummy node相连。

Code

class Solution:
    class UF:        
        def __init__(self, M, N):
            self.N = N
            self.parents = [0] * (M * N + 1)
            for i in range(len(self.parents)):
                self.parents[i] = i
            
        def un(self, r1, c1, r2, c2):
            x = self.find(r1 * self.N + c1 + 1)
            y = self.find(r2 * self.N + c2 + 1)
            self.parents[y] = x
            
        def find(self, x):
            while x != self.parents[x]:
                self.parents[x] = self.parents[self.parents[x]]
                x = self.parents[x]
            return x
        
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        M = len(board)
        N = len(board[0]) if M > 0 else 0
        uf = Solution.UF(M, N)
        cnt = 0
        for i in range(M):
            for j in range(N):
                if board[i][j] == 'X':
                    continue
                if i == 0 or i == M - 1 or j == 0 or j == N - 1:
                    uf.parents[i * N + j + 1] = 0
                if i - 1 >= 0 and board[i - 1][j] == 'O':
                    uf.un(i - 1, j, i, j)
                if j - 1 >= 0 and board[i][j - 1] == 'O':
                    uf.un(i, j - 1, i, j)
        z = uf.find(0)
        for i in range(M):
            for j in range(N):
                if board[i][j] == 'X':
                    continue
                x = uf.find(i * N + j + 1)
                if x == z:
                    continue
                board[i][j] = 'X'
    

class Solution {
    class UnionFind {
        int[] fathers;
        int n;
        int count = 0;
        UnionFind(char[][] board) {
            int m = board.length;
            n = board[0].length;
            fathers = new int[m * n + 1];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == 'O') {
                        int id = i * n + j;
                        fathers[id] = id;
                        count++;   
                    }
                }
            }
            fathers[m * n] = m * n;
            count++;
        }

        public int find(int x, int y) {
            return find(x * n + y);
        }

        public void union(int x1, int y1, int x2, int y2) {
            union(x1 * n + y1, x2 * n + y2);
        }

        public int find(int id) {
            if (id == fathers[id]) {
                return id;
            }
            fathers[id] = find(fathers[id]);
            return fathers[id];
        }

        public void union(int id1, int id2) {
            int find1 = find(id1);
            int find2 = find(id2);
            if (find1 != find2) {
                fathers[find1] = find2;
                count--;
            }
        }
    }


    public void solve(char[][] board) {
        if (board.length == 0) {
            return;
        }
        int[][] dirs = new int[][]{{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
        UnionFind uf = new UnionFind(board);
        int n = board[0].length;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 'O') {
                    for (int[] dir : dirs) {
                        int x = i + dir[0];
                        int y = j + dir[1];
                        if (x >= 0 && x < board.length && y >= 0 && y < board[0].length) {
                            if (board[x][y] == 'O') {
                                uf.union(i, j, x, y);
                            }
                        } else {
                            uf.union(i * n + j, board.length * n);
                        }
                    }
                }
            }
        }

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

    }
}

Analysis

时间复杂度不超过O(N^3), 空间复杂度O(N).