SurroundedRegions [source code]
public class SurroundedRegions {
static
/******************************************************************************/
class Solution {
static int[] directions = {-1, 0, 1, 0, -1};
public void solve(char[][] board) {
if (board.length == 0 || board[0].length == 0)
return;
boolean[][] visited = new boolean[board.length][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' && !visited[i][j])
dfs (board, i, j, visited);
}
void dfs (char[][] board, int rx, int ry, boolean[][] visited) {
Pair root = new Pair (rx, ry);
Deque<Pair> stack = new ArrayDeque<> ();
boolean surrounded = true;
stack.push (root);
while (!stack.isEmpty ()) {
Pair cur = stack.pop ();
for (int j = 0; j < 4; j++) {
int nx = cur.x + directions[j], ny = cur.y + directions[j + 1];
if (!inBound (board, nx, ny)) {
surrounded = false;
} else if (board[nx][ny] == 'O' && !visited[nx][ny]) {
visited[nx][ny] = true;
stack.push (new Pair (nx, ny));
}
}
}
if (!surrounded)
return;
stack.clear ();
stack.push (root);
while (!stack.isEmpty ()) {
Pair cur = stack.pop ();
for (int j = 0; j < 4; j++) {
int nx = cur.x + directions[j], ny = cur.y + directions[j + 1];
board[cur.x][cur.y] = 'X';
if (inBound (board, nx, ny) && board[nx][ny] == 'O')
stack.push (new Pair (nx, ny));
}
}
}
void bfs (char[][] board, int rx, int ry, boolean[][] visited) {
Pair root = new Pair (rx, ry);
Queue<Pair> queue = new LinkedList<> ();
boolean surrounded = true;
queue.offer (root);
while (!queue.isEmpty ()) {
int size = queue.size ();
for (int i = 0; i < size; i++) {
Pair cur = queue.poll ();
for (int j = 0; j < 4; j++) {
int nx = cur.x + directions[j], ny = cur.y + directions[j + 1];
if (!inBound (board, nx, ny)) {
surrounded = false;
} else if (board[nx][ny] == 'O' && !visited[nx][ny]) {
visited[nx][ny] = true;
queue.offer (new Pair (nx, ny));
}
}
}
}
if (!surrounded)
return;
queue.clear ();
queue.offer (root);
while (!queue.isEmpty ()) {
int size = queue.size ();
for (int i = 0; i < size; i++) {
Pair cur = queue.poll ();
board[cur.x][cur.y] = 'X';
for (int j = 0; j < 4; j++) {
int nx = cur.x + directions[j], ny = cur.y + directions[j + 1];
if (inBound (board, nx, ny) && board[nx][ny] == 'O')
queue.offer (new Pair (nx, ny));
}
}
}
}
boolean inBound (char[][] board, int x, int y) {
return x >= 0 && y >= 0 && x < board.length && y < board[0].length;
}
static class Pair {
int x, y;
Pair (int x, int y) {this.x = x; this.y = y; }
}
}
/******************************************************************************/
public static void main(String[] args) {
SurroundedRegions.Solution tester = new SurroundedRegions.Solution();
char[][][] inputs = {
{{'X','X','X','X'},{'X','O','O','X'},{'X','X','O','X'},{'X','O','X','X'}},
{{'X','X','X','X'},{'X','X','X','X'},{'X','X','X','X'},{'X','O','X','X'}}, //1
{{'O','O','O','O','O','O','O','O','X','O','O','O','O','O','X','O','O','O','O','O'},{'O','O','O','O','O','O','O','X','O','O','O','O','O','O','O','O','O','O','O','O'},{'X','O','O','X','O','X','O','O','O','O','X','O','O','X','O','O','O','O','O','O'},{'O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','X','X','O'},{'O','X','X','O','O','O','O','O','O','X','O','O','O','O','O','O','O','O','O','O'},{'O','O','O','O','X','O','O','O','O','O','O','X','O','O','O','O','O','X','X','O'},{'O','O','O','O','O','O','O','X','O','O','O','O','O','O','O','O','O','O','O','O'},{'O','O','O','O','O','O','O','O','O','O','O','O','O','X','O','O','O','O','O','O'},{'O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','X','O'},{'O','O','O','O','O','X','O','O','O','O','O','O','O','O','O','O','O','O','O','O'},{'O','O','O','O','O','O','O','O','X','O','O','O','O','O','O','O','O','O','O','O'},{'O','O','O','O','X','O','O','O','O','X','O','O','O','O','O','O','O','O','O','O'},{'O','O','O','O','O','O','O','O','X','O','O','O','O','O','O','O','O','O','O','O'},{'X','O','O','O','O','O','O','O','O','X','X','O','O','O','O','O','O','O','O','O'},{'O','O','O','O','O','O','O','O','O','O','O','X','O','O','O','O','O','O','O','O'},{'O','O','O','O','X','O','O','O','O','O','O','O','O','X','O','O','O','O','O','X'},{'O','O','O','O','O','X','O','O','O','O','O','O','O','O','O','X','O','X','O','O'},{'O','X','O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','O'},{'O','O','O','O','O','O','O','O','X','X','O','O','O','X','O','O','X','O','O','X'},{'O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','O'}},
{{'O','O','O','O','O','O','O','O','X','O','O','O','O','O','X','O','O','O','O','O'},{'O','O','O','O','O','O','O','X','O','O','O','O','O','O','O','O','O','O','O','O'},{'X','O','O','X','O','X','O','O','O','O','X','O','O','X','O','O','O','O','O','O'},{'O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','X','X','O'},{'O','X','X','O','O','O','O','O','O','X','O','O','O','O','O','O','O','O','O','O'},{'O','O','O','O','X','O','O','O','O','O','O','X','O','O','O','O','O','X','X','O'},{'O','O','O','O','O','O','O','X','O','O','O','O','O','O','O','O','O','O','O','O'},{'O','O','O','O','O','O','O','O','O','O','O','O','O','X','O','O','O','O','O','O'},{'O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','X','O'},{'O','O','O','O','O','X','O','O','O','O','O','O','O','O','O','O','O','O','O','O'},{'O','O','O','O','O','O','O','O','X','O','O','O','O','O','O','O','O','O','O','O'},{'O','O','O','O','X','O','O','O','O','X','O','O','O','O','O','O','O','O','O','O'},{'O','O','O','O','O','O','O','O','X','O','O','O','O','O','O','O','O','O','O','O'},{'X','O','O','O','O','O','O','O','O','X','X','O','O','O','O','O','O','O','O','O'},{'O','O','O','O','O','O','O','O','O','O','O','X','O','O','O','O','O','O','O','O'},{'O','O','O','O','X','O','O','O','O','O','O','O','O','X','O','O','O','O','O','X'},{'O','O','O','O','O','X','O','O','O','O','O','O','O','O','O','X','O','X','O','O'},{'O','X','O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','O'},{'O','O','O','O','O','O','O','O','X','X','O','O','O','X','O','O','X','O','O','X'},{'O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','O','O'}}, //2
};
for (int i = 0; i < inputs.length / 2; i++) {
System.out.println (Printer.separator ());
char[][] board = inputs[2 * i], ans = inputs[2 * i + 1];
String input_str = colorBoard (board), ans_str = colorBoard (ans);
tester.solve (board);
String output_str = colorBoard (board);
System.out.printf ("%s\n -> \n%s, expected: \n%s\n",
input_str, Printer.wrap (output_str, output_str.equals (ans_str) ? 92 : 91), ans_str
);
}
}
static String colorBoard (char[][] board) {
return Arrays.deepToString (board).replace ("],", "],\n").replace ("O", Printer.wrap ("O", 95));
}
}
这题的难点好像是这个surround的概念要求的是一个四边都要围住, 所以如果直接一个DFS找到所有的CC, 好像是不够的; 因为周围可能会碰到边界, 而边界是不算一个surround的;
有一个大概的思路, 可以这样, 在整个board的边缘, 相当于有一个假想的一层多出来的border, 如果一个CC能够接触到这个border, 那么这个整个CC都是没有被包围的;
那么相应的, DFS写的时候的order就要稍微注意一下, PreOrder(走到一个cell, 直接就flip)肯定是不行的, 要有一个PostOrder的过程, 只要child返回上来有一个是not surrounded, 那么整个都是not surrounded, 只有全部都是surrounded, 那么最后返回的才是surrounded, 这个时候flip当前的cell; 这个逻辑可以写写看, 暂时看起来好像没有什么问题;
很自然的写出来这个代码:
class Solution {
public void solve(char[][] board) {
if (board.length == 0 || board[0].length == 0)
return;
for (int i = 0; i < board.length; i++) for (int j = 0; j < board[0].length; j++) if (board[i][j] == 'O')
dfs (board, i, j, new boolean[board.length][board[0].length]);
}
boolean dfs (char[][] board, int x, int y, boolean[][] visited) {
if (x < 0 || y < 0 || x >= board.length || y >= board[0].length) // notice the order of base cases
return false;
if (visited[x][y] || board[x][y] != 'O') // sensitive to FALSE, so VISITED cells should not affect upper level decision;
return true;
visited[x][y] = true;
// take advantage of short-circuit
boolean surrounded =
dfs (board, x - 1, y, visited) &&
dfs (board, x + 1, y, visited) &&
dfs (board, x, y + 1, visited) &&
dfs (board, x, y - 1, visited);
visited[x][y] = false;
if (surrounded)
board[x][y] = 'X';
return surrounded;
}
}
虽然有几个小bug, 但是思路是对的, 然后我就知道这个题目为什么这么多的downvote了, 这个题目后面居然用大case把recursion给break了; 但是这题实际上用DFS是比BFS好的, 所以这里就是逼你自己实现一下Stack的DFS, 而且是PostOrder的;
这个就有点恶心人了;
另外, 到这里看来, 好像知道为什么这题UF好像还不错了, 就是我个人不太熟悉, 没把握写得好;
大概回顾了一下自己之前DFS的总结, 感觉还是geeks4geeks上面看来的那个traversal based的方法更加好写, 这种写法注意第一个branch里面的那个else;
第二种我自己想出来的那个虽然看起来slick, 但是不是特别的好理解: 人工的通过next来控制cur是否变成Null来出发对Stack的访问;
突然想到这个问题的DFS更难的一个地方: 这个tree不是binary的;
另外, 没有一个自然定义的Null, 这里的Null到底是怎么理解? visited? 出界? X?
回头又想了一下, 上面这个recursion算法好像其实是有问题的:
你看这里这个例子, 向右的这个child(1,2), 是被包围的, 所以他自己就会立刻flip, 但是实际上向下有一个free的cell, 所以(1,1)是不会被flip, 但是我们已经把(1,2)给错flip了; 这个题目感觉还是比想象的有难度; 一个折衷的办法就是只能用2pass来做, 避免这种手太快导致的错误, 也就是假如当前cell的surrounded是true, 那么可以比如, 不undo visited; 不行;
话说回来, 既然原因2pass了, 这个题目就未必必须用DFS了? 而且上面看来, DFS对于这题并没有什么特殊的优势了; 不如直接先一个BFS走一下, 看看是不是surrounded, 如果true, 再走一个2pass来flip就行了;
注意, 第一个pass的BFS找边界出口cell的时候, 不要premature exit; 因为还是要把当前的CC里面的所有的cell都标记成visited, 这样后面不会重复搜索这个CC;
mark visited when push
写了一个BFS代码, 结果还是被上面的test2给break掉了; 仔细思考了一下, 好像是因为BFS的时候有一个以前总结过的问题: 如果BFS的不同path之间的overlapping太多, 而你的mark visited又是在Poll的时候做的话, 最后会有大量重复的push;
不想写DFS, 不过这题实际上DFS也没问题? 因为不用管order; 或者直接改这个BFS, 在push的时候visited?
事实上这题肯定还是DFS更加合理的;
这样一个代码, 在解决了上面visited的问题之后, 还是被一个200x200的test给break掉了:
class Solution {
static int[] directions = {-1, 0, 1, 0, -1};
public void solve(char[][] board) {
if (board.length == 0 || board[0].length == 0)
return;
boolean[][] visited = new boolean[board.length][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' && !visited[i][j])
bfs (board, i, j, visited);
}
void bfs (char[][] board, int rx, int ry, boolean[][] visited) {
Pair root = new Pair (rx, ry);
Queue<Pair> queue = new LinkedList<> ();
boolean surrounded = true;
queue.offer (root);
while (!queue.isEmpty ()) {
int size = queue.size ();
for (int i = 0; i < size; i++) {
Pair cur = queue.poll ();
for (int j = 0; j < 4; j++) {
int nx = cur.x + directions[j], ny = cur.y + directions[j + 1];
if (!inBound (board, nx, ny)) {
surrounded = false;
} else if (board[nx][ny] == 'O' && !visited[nx][ny]) {
visited[nx][ny] = true;
queue.offer (new Pair (nx, ny));
}
}
}
}
if (!surrounded)
return;
queue.clear ();
queue.offer (root);
while (!queue.isEmpty ()) {
int size = queue.size ();
for (int i = 0; i < size; i++) {
Pair cur = queue.poll ();
board[cur.x][cur.y] = 'X';
for (int j = 0; j < 4; j++) {
int nx = cur.x + directions[j], ny = cur.y + directions[j + 1];
if (inBound (board, nx, ny) && board[nx][ny] == 'O')
queue.offer (new Pair (nx, ny));
}
}
}
}
boolean inBound (char[][] board, int x, int y) {
return x >= 0 && y >= 0 && x < board.length && y < board[0].length;
}
static class Pair {
int x, y;
Pair (int x, int y) {this.x = x; this.y = y; }
}
}
快速写一个DFS版本, 看看行不行, 不行就真的拉倒了;
我操居然AC了; BFS版本和DFS版本都保留在上面了; 速度是28ms (6%), 毕竟是一个2pass的做法, 不算快;
没有editorial;
First, check the four border of the matrix. If there is a element is
- ’O’, alter it and all its neighbor ‘O’ elements to ‘1’.
- Then ,alter all the ‘O’ to ‘X’
- At last,alter all the ‘1’ to ‘O’
For example:
X X X X X X X X X X X X X X O X -> X X O X -> X X X X X O X X X 1 X X X O X X X O X X X 1 X X X O X X
class Solution {
public:
void solve(vector<vector<char>>& board) {
int i,j;
int row=board.size();
if(!row)
return;
int col=board[0].size();
for(i=0;i<row;i++){
check(board,i,0,row,col);
if(col>1)
check(board,i,col-1,row,col);
}
for(j=1;j+1<col;j++){
check(board,0,j,row,col);
if(row>1)
check(board,row-1,j,row,col);
}
for(i=0;i<row;i++)
for(j=0;j<col;j++)
if(board[i][j]=='O')
board[i][j]='X';
for(i=0;i<row;i++)
for(j=0;j<col;j++)
if(board[i][j]=='1')
board[i][j]='O';
}
void check(vector<vector<char> >&vec,int i,int j,int row,int col){
if(vec[i][j]=='O'){
vec[i][j]='1';
if(i>1)
check(vec,i-1,j,row,col);
if(j>1)
check(vec,i,j-1,row,col);
if(i+1<row)
check(vec,i+1,j,row,col);
if(j+1<col)
check(vec,i,j+1,row,col);
}
}
};
想法相当的直接, 代码组织的也很好; 很丢人, 我居然没有想到这个做法, 这个做法本身真的不难; 我感觉我还是有点犯了太追求generic的毛病; 总是想着找CC, 然后还要找边界, 这些看起来很slick的点子; 但是实际上这题的本质, 就是CC涂, 但是有出口的CC除外: 那做法就很简单, 直接先把有出口的CC全都关了就行了;
一个问题是, 上面这个人的DFS为什么没有被break, 果然下面有人实锤了:
This is a DFS solution, but it may causes a stack overflow issue.
When you use DFS, it is tricky to use:if(i>1) check(vec,i-1,j,row,col); if(j>1) check(vec,i,j-1,row,col);because it is more common to write like this:
if(i>=1) check(vec,i-1,j,row,col); if(j>=1) check(vec,i,j-1,row,col);Then I’ll explain it.
There is a test case like this:OOOOOOOOOO XXXXXXXXXO OOOOOOOOOO OXXXXXXXXX OOOOOOOOOO XXXXXXXXXO OOOOOOOOOO OXXXXXXXXX OOOOOOOOOO XXXXXXXXXOTo make it clear, I draw a 10x10 board, but it is actually a 250x250 board like this one.
When dfs function visit board[0][0], it ought to visit every grid marked ‘O’, thus lead to stack overflow(runtime error).
After you change “if(j>=1)” to “if(j>1)”, the DFS function won’t check board[i][0] (0<=i<=row-1), and then not all the grids marked ‘O’ will be visited when you dfs(board[0][0]).
Your code won’t cause stack overflow in this test case, but if we change the test case a little, it won’t work well.
Consider a test case like this:OOOOOOOOOOOX XXXXXXXXXXOX XOOOOOOOOOOX XOXXXXXXXXXX XOOOOOOOOOOX XXXXXXXXXXOX XOOOOOOOOOOX XOXXXXXXXXXX XOOOOOOOOOOX XXXXXXXXXXOXI draw a 10x12 board, but it may be as large as the 250x250 board.
I believe that your code will get “runtime error” in this test case when tested in Leetcode system.
这个可以说是相当的眼尖了; 虽然这题, 避免recurse到border是没有关系的, 但是假如一个更大的board, 然后在-2层的border也有O, 那么就有可能继续爆栈了;
Quite readable code! Just a slight improvement: your last part can be replaced by the following:
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++)
board[i][j] = (board[i][j] == '1') ? 'O' : 'X';
反正这里的核心思想还是学到了先把border上的CC关了; 估计大部分很快的解法都是这个思路; 这样剩下来的工作全都是普通循环能做的, 不需要用collection来做各种操作;
https://leetcode.com/problems/surrounded-regions/discuss/41630/9-lines-Python-148-ms
Phase 1: “Save” every O-region touching the border, changing its cells to ‘S’.
Phase 2: Change every ‘S’ on the board to ‘O’ and everything else to ‘X’.
def solve(self, board):
if not any(board): return
m, n = len(board), len(board[0])
save = [ij for k in range(m+n) for ij in ((0, k), (m-1, k), (k, 0), (k, n-1))]
while save:
i, j = save.pop()
if 0 <= i < m and 0 <= j < n and board[i][j] == 'O':
board[i][j] = 'S'
save += (i, j-1), (i, j+1), (i-1, j), (i+1, j)
board[:] = [['XO'[c == 'S'] for c in row] for row in board]
In case you don’t like my last line, you could do this instead:
for row in board:
for i, c in enumerate(row):
row[i] = 'XO'[c == 'S']
有一行的语法看不懂, 自己试了一下:
In [1]: [ij for k in range(7) for ij in range(5)]
Out[1]:
[0,
1,
2,
3,
4,
0,
1,
2,
3,
4,
0,
1,
2,
3,
4,
0,
1,
2,
3,
4,
0,
1,
2,
3,
4,
0,
1,
2,
3,
4,
0,
1,
2,
3,
4]
好像就是一个两层循环的意思, 从左到右是从外到内;
这也是为什么Stefan这里原来的代码里面, 第二个for里面可以使用k;
for k in range(max(m,n)) , better?
@sanderszzw Ah, yes, possibly. I suspected they just saw the loop and no recursion and equated that with BFS. Some people do that. But you’re right, my initialization is BFS-like (I say “-like” because it’s really just one level and not much of a search).
其他思路基本是类似的;
https://leetcode.com/problems/surrounded-regions/discuss/41617/Solve-it-using-Union-Find
class UF
{
private:
int* id; // id[i] = parent of i
int* rank; // rank[i] = rank of subtree rooted at i (cannot be more than 31)
int count; // number of components
public:
UF(int N)
{
count = N;
id = new int[N];
rank = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
rank[i] = 0;
}
}
~UF()
{
delete [] id;
delete [] rank;
}
int find(int p) {
while (p != id[p]) {
id[p] = id[id[p]]; // path compression by halving
p = id[p];
}
return p;
}
int getCount() {
return count;
}
bool connected(int p, int q) {
return find(p) == find(q);
}
void connect(int p, int q) {
int i = find(p);
int j = find(q);
if (i == j) return;
if (rank[i] < rank[j]) id[i] = j;
else if (rank[i] > rank[j]) id[j] = i;
else {
id[j] = i;
rank[i]++;
}
count--;
}
};
class Solution {
public:
void solve(vector<vector<char>> &board) {
int n = board.size();
if(n==0) return;
int m = board[0].size();
UF uf = UF(n*m+1);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if((i==0||i==n-1||j==0||j==m-1)&&board[i][j]=='O') // if a 'O' node is on the boundry, connect it to the dummy node
uf.connect(i*m+j,n*m);
else if(board[i][j]=='O') // connect a 'O' node to its neighbour 'O' nodes
{
if(board[i-1][j]=='O')
uf.connect(i*m+j,(i-1)*m+j);
if(board[i+1][j]=='O')
uf.connect(i*m+j,(i+1)*m+j);
if(board[i][j-1]=='O')
uf.connect(i*m+j,i*m+j-1);
if(board[i][j+1]=='O')
uf.connect(i*m+j,i*m+j+1);
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(!uf.connected(i*m+j,n*m)){ // if a 'O' node is not connected to the dummy node, it is captured
board[i][j]='X';
}
}
}
}
};
Hi. So here is my accepted code using Union Find data structure. The idea comes from the observation that if a region is NOT captured, it is connected to the boundry. So if we connect all the ‘O’ nodes on the boundry to a dummy node, and then connect each ‘O’ node to its neighbour ‘O’ nodes, then we can tell directly whether a ‘O’ node is captured by checking whether it is connected to the dummy node.
For more about Union Find, the first assignment in the algo1 may help:
https://www.coursera.org/course/algs4partI
想法还是不错的, 不过对于这题确实是复杂的, 说到底就是对于border上面的CC进行特殊处理, intermediate state明显更加容易;
不过他这个实现的还是不错的, 虽然说看起来代码有点长, 但是实际上逻辑很清晰, 就包括path compression都加进去了也不复杂;
UF summary
- 维护两个array, 一个是每一个element的parent ID, 也就是自己的group ID, 一个是维护每一个element所在group(注意index还是element而不是group head)的rank, 或者说size, 或者both;
- 提供三个method, 一个find(要包含path compression), 一个union, 一个是is_unioned.
另外, 他这里所有的element都用1D的index来表示, 也是为了让array组织的时候更加方便;
public class Solution {
int[] unionSet; // union find set
boolean[] hasEdgeO; // whether an union has an 'O' which is on the edge of the matrix
public void solve(char[][] board) {
if(board.length == 0 || board[0].length == 0) return;
// init, every char itself is an union
int height = board.length, width = board[0].length;
unionSet = new int[height * width];
hasEdgeO = new boolean[unionSet.length];
for(int i = 0;i<unionSet.length; i++) unionSet[i] = i;
for(int i = 0;i<hasEdgeO.length; i++){
int x = i / width, y = i % width;
hasEdgeO[i] = (board[x][y] == 'O' && (x==0 || x==height-1 || y==0 || y==width-1));
}
// iterate the matrix, for each char, union it + its upper char + its right char if they equals to each other
for(int i = 0;i<unionSet.length; i++){
int x = i / width, y = i % width, up = x - 1, right = y + 1;
if(up >= 0 && board[x][y] == board[up][y]) union(i,i-width);
if(right < width && board[x][y] == board[x][right]) union(i,i+1);
}
// for each char in the matrix, if it is an 'O' and its union doesn't has an 'edge O', the whole union should be setted as 'X'
for(int i = 0;i<unionSet.length; i++){
int x = i / width, y = i % width;
if(board[x][y] == 'O' && !hasEdgeO[findSet(i)])
board[x][y] = 'X';
}
}
private void union(int x,int y){
int rootX = findSet(x);
int rootY = findSet(y);
// if there is an union has an 'edge O',the union after merge should be marked too
boolean hasEdgeO = this.hasEdgeO[rootX] || this.hasEdgeO[rootY];
unionSet[rootX] = rootY;
this.hasEdgeO[rootY] = hasEdgeO;
}
private int findSet(int x){
if(unionSet[x] == x) return x;
unionSet[x] = findSet(unionSet[x]);
return unionSet[x];
}
}
类似的思路, 他union(i,i-width)这个操作有点有趣; 注意他这里是没有rank的, 所以union的时候的方式有点姜, 讲道理, 加一个rank好像其实也不是特别麻烦;
说到这里, 当初学这个的时候, 为什么教的做法是记录rank并且用rank来决胜负而不是size? 感觉这中间还是有一点理论上的原因的;
他这里是一个recursive的find, 而且实现了path compression;
Nice thought. I came up with this Java union-find with path compression and weighted union. Currently its run time is 17 ms. Can this be further improved? Thank you.
public class Solution {
private int[] ids;
// Weight (size) of each union set
private int[] sizes;
// The id of union set for 'O's on edge
private int OOnEdge;
int m;
int n;
public void solve(char[][] board) {
if((m = board.length) == 0 || (n = board[0].length) == 0) return;
ids = new int[m * n];
sizes = new int[m * n];
Arrays.fill(sizes, 1);
OOnEdge = -1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'X') {
continue;
}
int index = i * n + j;
ids[index] = index;
// Nodes on edges
if (i == 0 || j == 0 || i == m - 1 || j == n - 1) {
if (OOnEdge == -1) {
// Set OOnEdge if it has not been set yet
OOnEdge = index;
} else {
// If OOnEdge is already set, unite it with index
unite(OOnEdge, index);
}
}
// Unite node with its upper neighbor
if (i > 0 && board[i - 1][j] == 'O') {
unite(index, index - n);
}
// Unite node with its left neighbor
if (j > 0 && board[i][j - 1] == 'O') {
unite(index, index - 1);
}
}
}
// Find
for (int i = 1; i < m - 1; i++) {
for (int j = 1; j < n - 1; j++) {
if (board[i][j] == 'X') {
continue;
}
int index = i * n + j;
if (OOnEdge == -1 || !find(index, OOnEdge)) {
board[i][j] = 'X';
}
}
}
}
private void unite(int a, int b){
int i = findRoot(a);
int j = findRoot(b);
// Weighted quick union
if (sizes[i] < sizes[j]) {
ids[i] = j;
sizes[j] += sizes[i];
} else {
ids[j] = i;
sizes[i] += sizes[j];
}
}
private boolean find(int a, int b){
return findRoot(a) == findRoot(b);
}
private int findRoot(int i) {
while (i != ids[i]) {
// Path compression
ids[i] = ids[ids[i]];
i = ids[i];
}
return i;
}
}
大概好像还是差不多的思路; 没想到UF这题这么快的, 讲道理也不是特别难实现;
two suggestions
- you can combine the initialization of unionSet[] and hasEdgeO[] together
- in the union part, you can only find and union "O"s, now you are doing union-find to all "x"s as well
这个有点道理;
submission最优解就是这个intermediate state的方法: 7(83):
class Solution {
public void solve(char[][] board) {
int row = board.length;
if (row == 0) {
return;
}
int col = board[0].length;
for (int i = 0; i < row; i++) {
check(board, i, 0, row, col);
if (col > 1) {
check(board, i, col - 1, row, col);
}
}
for (int j = 1; j < col - 1; j++) {
check(board, 0, j, row, col);
if (row > 1) {
check(board, row - 1, j, row, col);
}
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
board[i][j] = board[i][j] == '*' ? 'O' : 'X';
}
}
}
private void check(char[][] board, int i, int j, int row, int col) {
if (board[i][j] == 'O') {
board[i][j] = '*';
if (i > 1) {
check(board, i - 1, j, row, col);
}
if (j > 1) {
check(board, i, j - 1, row, col);
}
if (i + 1 < row) {
check(board, i + 1, j, row, col);
}
if (j + 1 < col) {
check(board, i, j + 1, row, col);
}
}
}
}
Problem 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.
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
Difficulty:Medium
Total Accepted:97.8K
Total Submissions:503.6K
Contributor:LeetCode
Related Topics
depth-first searchbreadth-first searchunion find
Similar Questions
Number of IslandsWalls and Gates