LeetCode – Surrounded Regions (Java)
Given a 2D board containing 'X' and '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,
This problem is similar to Number of Islands. In this problem, only the cells on the boarders can not be surrounded. So we can first merge those O's on the boarders like in Number of Islands and replace O's with '#', and then scan the board and replace all O's left (if any).
http://blog.csdn.net/linhuanmars/article/details/22904855
这个题目用到的方法是图形学中的一个常用方法：Flood fill算法，其实就是从一个点出发对周围区域进行目标颜色的填充。背后的思想就是把一个矩阵看成一个图的结构，每个点看成结点，而边则是他上下左右的相邻点，然后进行一次广度或者深度优先搜索。
每个结点改变次数不会超过一次，因而是O(m*n)的复杂度.空间上就是递归栈（深度优先搜索）或者是队列（广度优先搜索）的空间，同时存在的空间占用不会超过O(m+n)（以广度优先搜索为例，每次队列中的结点虽然会往四个方向拓展，但是事实上这些结点会有很多重复，假设从中点出发，可以想象最大的扩展不会超过一个菱形，也就是n/2*2+m/2*2=m+n，所以算法的空间复杂度是O(m+n)）。
http://huntfor.iteye.com/blog/2082657
Iterative DFS:
https://discuss.leetcode.com/topic/6496/my-java-o-n-2-accepted-solution
BFS:
https://shawnlincoding.wordpress.com/2015/03/21/surrounded-regions/
https://leetcode.com/discuss/19805/my-java-o-n-2-accepted-solution
接下来我们看看这个题如何用Flood fill算法来解决。首先根据题目要求，边缘上的’O’是不需要填充的，所以我们的办法是对上下左右边缘做Flood fill算法，把所有边缘上的’O’都替换成另一个字符，比如’#’。接下来我们知道除去被我们换成’#’的那些顶点，剩下的所有’O’都应该被替换成’X’，而’#’那些最终应该是还原成’O’，如此我们可以做最后一次遍历，然后做相应的字符替换就可以了。复杂度分析上，我们先对边缘做Flood fill算法，因为只有是’O’才会进行，而且会被替换成’#’，所以每个结点改变次数不会超过一次，因而是O(m*n)的复杂度，最后一次遍历同样是O(m*n)，所以总的时间复杂度是O(m*n)。空间上就是递归栈（深度优先搜索）或者是队列（广度优先搜索）的空间，同时存在的空间占用不会超过O(m+n)（以广度优先搜索为例，每次队列中的结点虽然会往四个方向拓展，但是事实上这些结点会有很多重复，假设从中点出发，可以想象最大的扩展不会超过一个菱形，也就是n/2*2+m/2*2=m+n，所以算法的空间复杂度是O(m+n)
http://blog.welkinlan.com/2015/11/17/surrounded-regions-leetcode-java/
We can use Queue, remove and add
A little different BFS: SPace: O(MN)
http://yucoding.blogspot.com/2013/08/leetcode-question-131-surrounded-regions.html
http://www.cnblogs.com/huntfor/p/3898068.html
http://fisherlei.blogspot.com/2013/03/leetcode-surrounded-regions-solution.html
首先得想法就是BFS。对于每一个O，扫描其相邻节点，然后标示之，如果一个联通区域中有任何一个O在边界上，则保留之，否则清除该联通域
https://en.wikipedia.org/wiki/Flood_fill
The flood-fill algorithm takes three parameters: a start node, a target color, and a replacement color. The algorithm looks for all nodes in the array that are connected to the start node by a path of the target color and changes them to the replacement color.
Most practical implementations use a loop for the west and east directions as an optimization to avoid the overhead of stack or queue management: //TODO
X. Union Find
https://aaronice.gitbooks.io/lintcode/union_find/surrounded_regions.html
https://segmentfault.com/a/1190000007010346
思路1：和Number of Islands类似，但是此题用DFS会栈溢出，因此使用BFS。从四个边缘的元素开始BFS, 遇到 O 改成特殊字符M,最后没有被修改的O就是被X包围的，应当改为X, 并且把M恢复成O即可。 BFS搜索时队列中维护的是所有未展开BFS的 O，队列记录这些 O的位置。
思路2：利用union find算法，将所有边界可达的O union在一起。设置一个根节点oRoot，边界上的所有O同其union上，非边界的O同其上下左右的O进行union。扫描完board后，那些最终没有和oRoot union在一起的O是需要翻转的。实现时特别注意要将oRoot的秩设得足够大，比如设为矩阵元素个数，确保每个oRoot始终是边界可达O集合的根元素。因为在大矩阵情况下，中间可能产生比较大的秩，若oRoot秩比较小，根元素会被替换从而出错。
对比Number of Islands, 这里使用一维数组实现union find内部数据结构更简洁。
https://leetcode.com/problems/surrounded-regions/discuss/41617/Solve-it-using-Union-Find
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.
Given a 2D board containing 'X' and '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 XAfter running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
This problem is similar to Number of Islands. In this problem, only the cells on the boarders can not be surrounded. So we can first merge those O's on the boarders like in Number of Islands and replace O's with '#', and then scan the board and replace all O's left (if any).
http://blog.csdn.net/linhuanmars/article/details/22904855
这个题目用到的方法是图形学中的一个常用方法：Flood fill算法，其实就是从一个点出发对周围区域进行目标颜色的填充。背后的思想就是把一个矩阵看成一个图的结构，每个点看成结点，而边则是他上下左右的相邻点，然后进行一次广度或者深度优先搜索。
每个结点改变次数不会超过一次，因而是O(m*n)的复杂度.空间上就是递归栈（深度优先搜索）或者是队列（广度优先搜索）的空间，同时存在的空间占用不会超过O(m+n)（以广度优先搜索为例，每次队列中的结点虽然会往四个方向拓展，但是事实上这些结点会有很多重复，假设从中点出发，可以想象最大的扩展不会超过一个菱形，也就是n/2*2+m/2*2=m+n，所以算法的空间复杂度是O(m+n)）。
- DFS find all 'O' not surrounded by 'X' (at or connected to the edge of the board ) and changed to '#'
- Flip the remain 'O' into X
- Flip the '#' back to 'O'
public void solve(char[][] board) { if(board == null || board.length==0) return; int m = board.length; int n = board[0].length; //merge O's on left & right boarder for(int i=0;i<m;i++){ if(board[i][0] == 'O'){ merge(board, i, 0); } if(board[i][n-1] == 'O'){ merge(board, i,n-1); } } //merge O's on top & bottom boarder for(int j=0; j<n; j++){ if(board[0][j] == 'O'){ merge(board, 0,j); } if(board[m-1][j] == 'O'){ merge(board, m-1,j); } } //process the board for(int i=0;i<m;i++){ for(int j=0; j<n; j++){ if(board[i][j] == 'O'){ board[i][j] = 'X'; }else if(board[i][j] == '#'){ board[i][j] = 'O'; } } } } public void merge(char[][] board, int i, int j){ if(i<0 || i>=board.length || j<0 || j>=board[0].length) return; if(board[i][j] != 'O') return; board[i][j] = '#'; merge(board, i-1, j); merge(board, i+1, j); merge(board, i, j-1); merge(board, i, j+1); }https://leetcode.com/discuss/59652/java-boundary-turning-solution-simple-clean-code-commented
http://huntfor.iteye.com/blog/2082657
Code would be cleaner if we check condition in base condition
http://bangbingsyb.blogspot.com/2014/11/leetcode-surrounded-regions.htmlIterative DFS:
void solve(vector<vector<char>> &board) { if(board.size()<3 || board[0].size()<3) return; fillBorders(board, 'O', 'Y'); replace(board, 'O', 'X'); fillBorders(board, 'Y', 'O'); } void fill(vector<vector<char>> &board, int i, int j, char target, char c) { int m = board.size(), n = board[0].size(); if(i<0 || j<0 || i>=m || j>=n || board[i][j]!=target) return; stack<pair<int,int>> s; s.push(make_pair(i,j)); while(!s.empty()) { i = s.top().first; j = s.top().second; s.pop(); board[i][j] = c; if(i>0 && board[i-1][j]==target) s.push(make_pair(i-1,j)); if(i<m-1 && board[i+1][j]==target) s.push(make_pair(i+1,j)); if(j>0 && board[i][j-1]==target) s.push(make_pair(i,j-1)); if(j<n-1 && board[i][j+1]==target) s.push(make_pair(i,j+1)); } } void fillBorders(vector<vector<char>> &board, char target, char c) { int m = board.size(), n = board[0].size(); for(int i=0; i<m; i++) { if(board[i][0]==target) fill(board, i, 0, target, c); if(board[i][n-1]==target) fill(board, i, n-1, target, c); } for(int j=1; j<n-1; j++) { if(board[0][j]==target) fill(board, 0, j, target, c); if(board[m-1][j]==target) fill(board, m-1, j, target, c); } } void replace(vector<vector<char>> &board, char target, char c) { int m = board.size(), n = board[0].size(); for(int i=0; i<m; i++) { for(int j=0; j<n; j++) { if(board[i][j]==target) board[i][j] = c; } } }
https://discuss.leetcode.com/topic/6496/my-java-o-n-2-accepted-solution
public void markUnflippable(char[][] board, int r, int c) {
int[] dirX = {-1,0,1,0};
int[] dirY = {0,1,0,-1};
ArrayDeque<Pair> stack = new ArrayDeque<>();
stack.push(new Pair(r,c));
while(!stack.isEmpty()) {
Pair p = stack.pop();
board[p.first][p.second] = 'U';
for(int i = 0; i < dirX.length; ++i) {
if(p.first + dirX[i] >= 0 && p.first + dirX[i] < board.length && p.second + dirY[i] >= 0 && p.second +dirY[i] < board[p.first + dirX[i]].length && board[p.first+dirX[i]][p.second+dirY[i]] == 'O') {
stack.push(new Pair(p.first+dirX[i],p.second+dirY[i]));
}
}
}
}BFS:
https://shawnlincoding.wordpress.com/2015/03/21/surrounded-regions/
https://leetcode.com/discuss/19805/my-java-o-n-2-accepted-solution
接下来我们看看这个题如何用Flood fill算法来解决。首先根据题目要求，边缘上的’O’是不需要填充的，所以我们的办法是对上下左右边缘做Flood fill算法，把所有边缘上的’O’都替换成另一个字符，比如’#’。接下来我们知道除去被我们换成’#’的那些顶点，剩下的所有’O’都应该被替换成’X’，而’#’那些最终应该是还原成’O’，如此我们可以做最后一次遍历，然后做相应的字符替换就可以了。复杂度分析上，我们先对边缘做Flood fill算法，因为只有是’O’才会进行，而且会被替换成’#’，所以每个结点改变次数不会超过一次，因而是O(m*n)的复杂度，最后一次遍历同样是O(m*n)，所以总的时间复杂度是O(m*n)。空间上就是递归栈（深度优先搜索）或者是队列（广度优先搜索）的空间，同时存在的空间占用不会超过O(m+n)（以广度优先搜索为例，每次队列中的结点虽然会往四个方向拓展，但是事实上这些结点会有很多重复，假设从中点出发，可以想象最大的扩展不会超过一个菱形，也就是n/2*2+m/2*2=m+n，所以算法的空间复杂度是O(m+n)
public void solve(char[][] board) { if(board == null || board.length == 0){ return; } int m = board.length, n = board[0].length; for(int i = 0; i < m; i++){ helper(board, i, 0); helper(board, i, n - 1); } for(int i = 0; i < n; i++){ helper(board, 0, i); helper(board, m - 1, i); } for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(board[i][j] == '#'){ board[i][j] = 'O'; }else if(board[i][j] == 'O'){ board[i][j] = 'X'; } } } } private void helper(char[][] board, int i, int j){ if(board[i][j] != 'O'){ return; } int m = board.length, n = board[0].length; board[i][j] = '#'; Queue<Integer> queue = new LinkedList<Integer>(); queue.offer(i * n + j); while(!queue.isEmpty()){ int pos = queue.poll(); int row = pos / n, col = pos % n; if(row > 0 && board[row - 1][col] == 'O'){ queue.offer((row - 1) * n + col); board[row - 1][col] = '#'; } if(row < m - 1 && board[row + 1][col] == 'O'){ queue.offer((row + 1) * n + col); board[row + 1][col] = '#'; } if(col > 0 && board[row][col - 1] == 'O'){ queue.offer(row * n + col - 1); board[row][col - 1] = '#'; } if(col < n - 1 && board[row][col + 1] == 'O'){ queue.offer(row * n + col + 1); board[row][col + 1] = '#'; } } }// use a queue to do BFS private Queue<Integer> queue = new LinkedList<Integer>(); public void solve(char[][] board) { if (board == null || board.length == 0) return; int m = board.length; int n = board[0].length; // merge O's on left & right boarder for (int i = 0; i < m; i++) { if (board[i][0] == 'O') { bfs(board, i, 0); } if (board[i][n - 1] == 'O') { bfs(board, i, n - 1); } } // merge O's on top & bottom boarder for (int j = 0; j < n; j++) { if (board[0][j] == 'O') { bfs(board, 0, j); } if (board[m - 1][j] == 'O') { bfs(board, m - 1, j); } } // process the board for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (board[i][j] == 'O') { board[i][j] = 'X'; } else if (board[i][j] == '#') { board[i][j] = 'O'; } } } } private void bfs(char[][] board, int i, int j) { int n = board[0].length; // fill current first and then its neighbors fillCell(board, i, j); while (!queue.isEmpty()) { int cur = queue.poll(); int x = cur / n; int y = cur % n; fillCell(board, x - 1, y); fillCell(board, x + 1, y); fillCell(board, x, y - 1); fillCell(board, x, y + 1); } } private void fillCell(char[][] board, int i, int j) { int m = board.length; int n = board[0].length; if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') return; // add current cell is queue & then process its neighbors in bfs queue.offer(i * n + j); board[i][j] = '#'; } |
We can use Queue, remove and add
public void solve(char[][] board) {
int row = board.length;
if (row == 0) return;
int col = board[0].length;
// store the index of '0'
ArrayList<Integer> xIndex = new ArrayList<Integer>();
ArrayList<Integer> yIndex = new ArrayList<Integer>();
// scan 4 sides of the matrix, store all 'O's
for (int i = 0; i < row; i++){
// left border
if (board[i][0] == 'O'){
xIndex.add(i);
yIndex.add(0);
}
// right border
if (board[i][col - 1] == 'O'){
xIndex.add(i);
yIndex.add(col - 1);
}
}
for (int i = 0; i < col; i++){
// top border
if (board[0][i] == 'O'){
xIndex.add(0);
yIndex.add(i);
}
// bottom border
if (board[row - 1][i] == 'O'){
xIndex.add(row - 1);
yIndex.add(i);
}
}
// iteratively (recursively) replace all 'O's connected to the 'O's on the sides as 'Y'
int k = 0;
while (k < xIndex.size()) {
int x = xIndex.get(k);
int y = yIndex.get(k);
board[x][y] = 'Y'; // this '0' is connected to '0's on the border, so it won't be flipped
// try 4 directions
if (x > 0 && board[x - 1][y] == 'O') {
xIndex.add(xIndex.size() - 1,x - 1);
yIndex.add(yIndex.size() - 1,y);
}
if (x < row - 1 && board[x + 1][y] == 'O') {
xIndex.add(xIndex.size() - 1,x + 1);
yIndex.add(yIndex.size() - 1,y);
}
if (y > 0 && board[x][y - 1] == 'O') {
xIndex.add(xIndex.size() - 1,x);
yIndex.add(yIndex.size() - 1,y - 1);
}
if (y<col-1 && board[x][y + 1] == 'O') {
xIndex.add(xIndex.size() - 1,x);
yIndex.add(yIndex.size() - 1,y + 1);
}
k++;
}
//recover all 'Y's as 'O', flip other 'O's as 'X'
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] == 'O') board[i][j] = 'X';
if (board[i][j] == 'Y') board[i][j] = 'O';
}
}
}
http://rleetcode.blogspot.com/2014/01/surround-regions-java.htmlA little different BFS: SPace: O(MN)
http://yucoding.blogspot.com/2013/08/leetcode-question-131-surrounded-regions.html
void solve(vector<vector<char>> &board) { int row = board.size(); //get row number if (row==0){return;} int col = board[0].size(); // get column number vector<vector<bool> > bb(row, vector<bool>(col)); //result vector queue<pair<int,int> > q; // queue for BFS //search "O" from 1st row for (int i=0;i<col;i++){ if (board[0][i]=='O'){ q.push(make_pair(0,i)); bb[0][i]=true; } } //search "O" from 1st column for (int i=0;i<row;i++){ if (board[i][0]=='O'){ q.push(make_pair(i,0)); bb[i][0]=true; } } //search "O" from last row for (int i=0;i<col;i++){ if (board[row-1][i]=='O'){ q.push(make_pair(row-1,i)); bb[row-1][i]=true; } } //search "O" from last column for (int i=0;i<row;i++){ if (board[i][col-1]=='O'){ q.push(make_pair(i,col-1)); bb[i][col-1]=true; } } //BFS int i,j; // current position while (!q.empty()){ //get current live "O" i = q.front().first; j = q.front().second; //pop up queue q.pop(); //search four directions if (i-1>0 && board[i-1][j]=='O' && bb[i-1][j]==false){bb[i-1][j]=true; q.push(make_pair(i-1,j));} //top if (i+1<row-1 && board[i+1][j]=='O'&& bb[i+1][j]==false){bb[i+1][j]=true; q.push(make_pair(i+1,j));} // bottom if (j-1>0 && board[i][j-1]=='O'&& bb[i][j-1]==false){bb[i][j-1]=true; q.push(make_pair(i,j-1));} // left if (j+1<col-1 && board[i][j+1]=='O'&& bb[i][j+1]==false){bb[i][j+1]=true; q.push(make_pair(i,j+1));} // right } //Get result for (int i=0;i<row;i++){ for (int j=0;j<col;j++){ if (board[i][j]=='O'&&bb[i][j]==false){ board[i][j]='X'; } } } return; }28 q.offer(i * code + j);//将二维下标压缩成一维，方便存储
30 int tem = q.poll(); 31 int row = tem / code; 32 int col = tem % code;
http://fisherlei.blogspot.com/2013/03/leetcode-surrounded-regions-solution.html
首先得想法就是BFS。对于每一个O，扫描其相邻节点，然后标示之，如果一个联通区域中有任何一个O在边界上，则保留之，否则清除该联通域
https://en.wikipedia.org/wiki/Flood_fill
The flood-fill algorithm takes three parameters: a start node, a target color, and a replacement color. The algorithm looks for all nodes in the array that are connected to the start node by a path of the target color and changes them to the replacement color.
Most practical implementations use a loop for the west and east directions as an optimization to avoid the overhead of stack or queue management: //TODO
Flood-fill (node, target-color, replacement-color): 1. Set Q to the empty queue. 2. If the color of node is not equal to target-color, return. 3. Add node to Q. 4. For each element N of Q: 5. Set w and e equal to N. 6. Move w to the west until the color of the node to the west of w no longer matches target-color. 7. Move e to the east until the color of the node to the east of e no longer matches target-color. 8. For each node n between w and e: 9. Set the color of n to replacement-color. 10. If the color of the node to the north of n is target-color, add that node to Q. 11. If the color of the node to the south of n is target-color, add that node to Q. 12. Continue looping until Q is exhausted. 13. Return.https://leetcode.com/discuss/26522/share-my-clean-java-code
X. Union Find
https://aaronice.gitbooks.io/lintcode/union_find/surrounded_regions.html
一种比较巧妙的思路是从边缘的'O'出发，通过DFS，所有能够遍历的'O'都可以暂时被标记为'#'，那么剩下未能被标记的'O'说明被surrounded，需要在遍历结束之后全部转为'X'。（用DFS或者BFS要警惕栈溢出）
另一种方法是用Union Find，将与边缘相连通的'O'全部union到一个dummy node（也可以用hasEdge[]来存储，不过内存占用更多）, 最终将没有和这个dummy node是一个component的'O'点全部标记为'X'。
https://segmentfault.com/a/1190000007010346
int row, col;
public void solve(char[][] board) {
if (board == null || board.length == 0) return;
row = board.length;
col = board[0].length;
UnionFind uf = new UnionFind(row*col+1);
int dummy = row*col;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] == 'O') {
if (i == 0 || i == row-1 || j == 0 || j == col-1) uf.union(node(i, j), dummy);
else {
if (i > 0 && board[i-1][j] == 'O') uf.union(node(i, j), node(i-1, j));
if (i > 0 && board[i+1][j] == 'O') uf.union(node(i, j), node(i+1, j));
if (j > 0 && board[i][j-1] == 'O') uf.union(node(i, j), node(i, j-1));
if (j > 0 && board[i][j+1] == 'O') uf.union(node(i, j), node(i, j+1));
}
}
}
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (uf.isConnected(node(i, j), dummy)) board[i][j] = 'O';
else board[i][j] = 'X';
}
}
}
public int node(int i, int j) {
return i*col+j;
}
}
class UnionFind {
int[] parents;
public UnionFind(int n) {
parents = new int[n];
for (int i = 0; i < n; i++) parents[i] = i;
}
public void union(int n1, int n2) {
int r1 = find(n1);
int r2 = find(n2);
if (r1 != r2) parents[r1] = r2;
}
public int find(int node) {
if (parents[node] == node) return node;
parents[node] = find(parents[node]);
return parents[node];
}
public boolean isConnected(int n1, int n2) {
return find(n1) == find(n2);
}
}思路1：和Number of Islands类似，但是此题用DFS会栈溢出，因此使用BFS。从四个边缘的元素开始BFS, 遇到 O 改成特殊字符M,最后没有被修改的O就是被X包围的，应当改为X, 并且把M恢复成O即可。 BFS搜索时队列中维护的是所有未展开BFS的 O，队列记录这些 O的位置。
思路2：利用union find算法，将所有边界可达的O union在一起。设置一个根节点oRoot，边界上的所有O同其union上，非边界的O同其上下左右的O进行union。扫描完board后，那些最终没有和oRoot union在一起的O是需要翻转的。实现时特别注意要将oRoot的秩设得足够大，比如设为矩阵元素个数，确保每个oRoot始终是边界可达O集合的根元素。因为在大矩阵情况下，中间可能产生比较大的秩，若oRoot秩比较小，根元素会被替换从而出错。
对比Number of Islands, 这里使用一维数组实现union find内部数据结构更简洁。
- public void solve(char[][] board) {
- if (board == null || board.length == 0 || board[0].length == 0)
- return;
- int rows = board.length, cols = board[0].length;
- int oRoot = rows * cols;
- initUnionFind(rows * cols);
- for (int i = 0; i < rows; i++) {
- for (int j = 0; j < cols; j++) {
- if (board[i][j] == 'X') continue;
- int curr = i * cols + j;
- if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1) {
- union(curr, oRoot);
- } else {
- if (j + 1 < cols && board[i][j + 1] == 'O')
- union(curr, i * cols + j + 1);
- if (j - 1 >= 0 && board[i][j - 1] == 'O')
- union(curr, i * cols + j - 1);
- if (i + 1 < rows && board[i + 1][j] == 'O')
- union(curr, (i + 1) * cols + j);
- if (i - 1 >= 0 && board[i - 1][j] == 'O')
- union(curr, (i - 1) * cols + j);
- }
- }
- }
- for (int i = 0; i < rows; i++) {
- for (int j = 0; j < cols; j++) {
- if (board[i][j] == 'O' && find(i * cols + j) != oRoot) {
- board[i][j] = 'X';
- }
- }
- }
- }
- int[] s;
- int[] rank;
- private void initUnionFind(int n) {
- s = new int[n + 1];
- rank = new int[n + 1];
- for (int i = 0; i <= n; i++)
- s[i] = i;
- rank[n] = n + 1; //??
- }
- private int find(int p) {
- if (s[p] == p) return p;
- else return s[p] = find(s[p]);
- }
- private void union(int p, int q) {
- int pRoot = find(p), qRoot = find(q);
- if (pRoot == qRoot) return;
- if (rank[pRoot] < rank[qRoot]) {
- s[pRoot] = qRoot;
- } else {
- if (rank[pRoot] == rank[qRoot])
- rank[pRoot]++;
- s[qRoot] = pRoot;
- }
- }
https://leetcode.com/problems/surrounded-regions/discuss/41617/Solve-it-using-Union-Find
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.
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];
}