130. Surrounded Regions

Leetcode Union Find Depth-First Search Breath-First Search

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.

分析

这道题其实思路是非常简单的：把二维数组放在UnionFind集合中，当出现'O'时，将'O'附近的'O'连接起来，形成connected component. 那么怎么判断'O'是否被围起来了呢？这里采用在原来数组外增加一圈'O'的方法，只需判断该'O'是否和外圈的'O'连接，来判断'O'是否被围起来。

public class Q130SurroundedRegions {
    public static void solve(char[][] board) {
        // corner case
        if (board.length < 3) return;

        int n = board.length;
        int m = board[0].length;

        // corner case
        if (m < 3) return;

        // add virtual points surrounds board
        int nn = n + 2, mm = m + 2;
        char[][] B = new char[nn][mm];
        for (int i = 0; i < nn; i++) {
            for (int j = 0; j < mm; j++) {
                if (i == 0 || j == 0 || j == mm - 1 || i == nn - 1)
                    B[i][j] = 'O';
                else
                    B[i][j] = board[i-1][j-1];
            }
        }



        // add union find data structure, 0 as virtual point
        WeightedPathCompressionQuickFind  uf = new WeightedPathCompressionQuickFind(nn*mm);
        int index;

        for (int i = 0; i < nn; i++) {
            for (int j = 0; j < mm; j++) {
                index = i * mm + j;

                if (virtualBoard[i][j] == 'O') {
                    // find adject 'O'
                    if ((j > 0) && (B[i][j-1] == 'O')) { //left
                        uf.union(index, index - 1);
                    }
                    if ((j < m - 1) && (B[i][j + 1] == 'O')) { // right
                        uf.union(index, index + 1);
                    }
                    if ((i > 0) && (B[i-1][j] == 'O')) { // top
                        uf.union(index, index - mm);
                    }
                    if ((i < n - 1) && (B[i+1][j] == 'O')) { // bottom
                        uf.union(index, index  + mm);
                    }
                }
            }
        }

        // flip it  if  'O' is captured,
        for (int i = 1; i < n - 1; i++) {
            for (int j = 1; j < m - 1; j++) {
                index = (i + 1) * mm + (j + 1); // index on virtual board
                if ((board[i][j] == 'O') && (!uf.connected(0, index))) {
                    board[i][j] = 'X';
                }
            }
        }
    }
}