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'; } } } } }
近期评论