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
Solution1：邊界DFS (Recursive)
(遞歸可能存在 stack overflow)
思路：找邊界聯(lián)通的所有的0，置為*。然后0置為X，*置為0
a最好在遞歸前就check是否visited或出界赃阀，如果沒有呐赡，再遞歸去visit
b或是寫法簡單的：直接dfs跨算，但每次進(jìn)入遞歸再檢查是否visited/出界
Time Complexity: O(mn) Space Complexity: O(mn)
Solution1.2：邊界DFS (Recursive) Round1
Time Complexity: O(mn) Space Complexity: O(mn)
Solution2：邊界DFS (stack)
思路：找聯(lián)通的所有的0，置為*舌缤。然后0置為X瓣距，*置為1
在放入stack前就check是否visited黔帕，如果沒有visit過，再放入stack
Time Complexity: O(mn) Space Complexity: O(mn)
Solution3：邊界BFS (queue)
思路：找聯(lián)通的所有的0蹈丸，置為*成黄。然后0置為X，*置為1
在放入queue前就check是否visited逻杖，如果沒有visit過慨默，再放入queue
Time Complexity: O(mn) Space Complexity: O(mn)
Solution4：Union Find
思路：每個位置的元素初始都assigned 一個id，并多建一個id[mn]作為邊緣標(biāo)志弧腥。遍歷將所有的0，若其是邊緣元素的話潮太，將其和"邊緣"id(id[mn]) union管搪，如果是中間元素虾攻，將其和周圍四鄰域的union。最終沒有和邊緣connected的置為'X'
Time Complexity: O(NlogN)? Space Complexity: O(N) N=m*n
Solution1a Code：
class Solution {
public void solve(char[][] board) {
if (board.length == 0 || board[0].length == 0)
return;
if (board.length < 2 || board[0].length < 2)
return;
int m = board.length, n = board[0].length;
//Any 'O' connected to a boundary can't be turned to 'X', so ...
//Start from first and last column, turn 'O' to '*'.
for (int i = 0; i < m; i++) {
if (board[i][0] == 'O')
boundaryDFS(board, i, 0);
if (board[i][n-1] == 'O')
boundaryDFS(board, i, n-1);
}
//Start from first and last row, turn '0' to '*'
for (int j = 0; j < n; j++) {
if (board[0][j] == 'O')
boundaryDFS(board, 0, j);
if (board[m-1][j] == 'O')
boundaryDFS(board, m-1, j);
}
//post-prcessing, turn 'O' to 'X', '*' back to 'O', keep 'X' intact.
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';
}
}
}
//Use DFS algo to turn internal however boundary-connected 'O' to '*';
private void boundaryDFS(char[][] board, int i, int j) {
//if (i < 0 || i > board.length - 1 || j < 0 || j > board[0].length - 1) return;
board[i][j] = '*';
if (i > 1 && board[i - 1][j] == 'O')
boundaryDFS(board, i - 1, j);
if (i < board.length - 2 && board[i + 1][j] == 'O')
boundaryDFS(board, i+1, j);
if (j > 1 && board[i][j - 1] == 'O')
boundaryDFS(board, i, j - 1);
if (j < board[i].length - 2 && board[i][j + 1] == 'O' )
boundaryDFS(board, i, j + 1);
}
}
Solution1b Code：
// overflow in this problem for some reason
//Use DFS algo to turn internal however boundary-connected 'O' to '*';
private void boundaryDFS(char[][] board, int i, int j) {
if (i < 0 || i > board.length - 1 || j < 0 || j > board[0].length - 1 || board[i][j] != 'O')
return;
board[i][j] = '*';
boundaryDFS(board, i - 1, j);
boundaryDFS(board, i + 1, j);
boundaryDFS(board, i, j - 1);
boundaryDFS(board, i, j + 1);
}
Solution1.2 Code：
class Solution {
public void solve(char[][] board) {
if(board == null || board.length == 0 || board[0].length == 0) return;
// dfs to find all 'O' that are connected to the edge
for(int row = 0; row < board.length; row++) {
if(board[row][0] == 'O') {
dfs(board, row, 0);
}
if(board[row][board[0].length - 1] == 'O') {
dfs(board, row, board[0].length - 1);
}
}
for(int col = 0; col < board[0].length; col++) {
if(board[0][col] == 'O') {
dfs(board, 0, col);
}
if(board[board.length - 1][col] == 'O') {
dfs(board, board.length - 1, col);
}
}
// flip
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
if(board[i][j] == 'O') {
board[i][j] = 'X';
}
else if(board[i][j] == 'E') {
board[i][j] = 'O';
}
}
}
}
private void dfs(char[][] board, int row, int col) {
board[row][col] = 'E';
if(row > 0 && board[row - 1][col] == 'O') {
dfs(board, row - 1, col);
}
if(row < board.length - 1 && board[row + 1][col] == 'O') {
dfs(board, row + 1, col);
}
if(col > 0 && board[row][col - 1] == 'O') {
dfs(board, row, col - 1);
}
if(col < board[0].length - 1 && board[row][col + 1] == 'O') {
dfs(board, row, col + 1);
}
}
}
Solution2 Code：
class Solution {
public void solve(char[][] board) {
if (board.length == 0 || board[0].length == 0)
return;
if (board.length < 2 || board[0].length < 2)
return;
int m = board.length, n = board[0].length;
Deque<Point> stack = new ArrayDeque<Point>();
//Any 'O' connected to a boundary can't be turned to 'X', so ...
//Start from first and last column, turn 'O' to '*'.
for (int i = 0; i < m; i++) {
if (board[i][0] == 'O') {
board[i][0] = '*';
stack.add(new Point(i, 0));
}
if (board[i][n - 1] == 'O') {
board[i][n - 1] = '*';
stack.add(new Point(i, n - 1));
}
}
//Start from first and last row, turn '0' to '*'
for (int j = 0; j < n; j++) {
if (board[0][j] == 'O') {
board[0][j] = '*';
stack.push(new Point(0, j));
}
if (board[m - 1][j] == 'O') {
board[m - 1][j] = '*';
stack.push(new Point(m - 1, j));
}
}
//BFS for the 'O's, and mark it as '+'
while (!stack.isEmpty()){
Point p = stack.pop();
int row = p.x;
int col = p.y;
if (row - 1 >= 0 && board[row - 1][col] == 'O') {
board[row - 1][col] = '*';
stack.push(new Point(row - 1, col));
}
if (row + 1 < m && board[row + 1][col] == 'O') {
board[row + 1][col] = '*';
stack.push(new Point(row + 1, col));
}
if (col - 1 >= 0 && board[row][col - 1] == 'O') {
board[row][col - 1] = '*';
stack.push(new Point(row, col - 1));
}
if (col + 1 < n && board[row][col + 1] == 'O') {
board[row][col + 1] = '*';
stack.push(new Point(row, col + 1));
}
}
//post-prcessing, turn 'O' to 'X', '*' back to 'O', keep 'X' intact.
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';
}
}
}
}
Solution3 Code：
class Solution {
public void solve(char[][] board) {
if (board.length == 0 || board[0].length == 0)
return;
if (board.length < 2 || board[0].length < 2)
return;
int m = board.length, n = board[0].length;
Queue<Point> queue = new LinkedList<Point>();
//Any 'O' connected to a boundary can't be turned to 'X', so ...
//Start from first and last column, turn 'O' to '*'.
for (int i = 0; i < m; i++) {
if (board[i][0] == 'O') {
board[i][0] = '*';
queue.add(new Point(i, 0));
}
if (board[i][n - 1] == 'O') {
board[i][n - 1] = '*';
queue.add(new Point(i, n - 1));
}
}
//Start from first and last row, turn '0' to '*'
for (int j = 0; j < n; j++) {
if (board[0][j] == 'O') {
board[0][j] = '*';
queue.add(new Point(0, j));
}
if (board[m - 1][j] == 'O') {
board[m - 1][j] = '*';
queue.add(new Point(m - 1, j));
}
}
//BFS for the 'O's, and mark it as '+'
while (!queue.isEmpty()){
Point p = queue.poll();
int row = p.x;
int col = p.y;
if (row - 1 >= 0 && board[row - 1][col] == 'O') {
board[row - 1][col] = '*';
queue.add(new Point(row - 1, col));
}
if (row + 1 < m && board[row + 1][col] == 'O') {
board[row + 1][col] = '*';
queue.add(new Point(row + 1, col));
}
if (col - 1 >= 0 && board[row][col - 1] == 'O') {
board[row][col - 1] = '*';
queue.add(new Point(row, col - 1));
}
if (col + 1 < n && board[row][col + 1] == 'O') {
board[row][col + 1] = '*';
queue.add(new Point(row, col + 1));
}
}
//post-prcessing, turn 'O' to 'X', '*' back to 'O', keep 'X' intact.
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';
}
}
}
}
Solution4 Code：
class Solution {
class UF {
private int[] id;
private int[] sz; // for an id, the number of elements in that id
private int count;
public UF(int m, int n) {
int N = m * n + 1;
this.id = new int[N];
this.sz = new int[N];
this.count = 0;
// init
for (int i = 0; i < N; i++) {
this.id[i] = i;
this.sz[i] = 1;
this.count++;
}
}
public void union(int p, int q) {
int p_root = find(p), q_root = find(q);
// weighted quick union
///*
if(p_root == q_root) return;
if (sz[p_root] < sz[q_root]) {
id[p_root] = q_root; sz[q_root] += sz[p_root];
} else {
id[q_root] = p_root; sz[p_root] += sz[q_root];
}
--count;
//*/
// regular
/*
if(p_root == q_root) return;
id[p_root] = q_root;
--count;
*/
}
public int find(int i) { // path compression
for (;i != id[i]; i = id[i])
id[i] = id[id[i]];
return i;
}
public boolean connected(int p, int q) {
int p_root = find(p);
int q_root = find(q);
if(p_root != q_root) return false;
else return true;
}
public int count() {
return this.count;
}
}
public void solve(char[][] board) {
if(board.length == 0 || board[0].length == 0) return;
int m = board.length, n = board[0].length;
UF uf = new UF(m, n);
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
// if a 'O' node is on the boundry, connect it to the dummy node. no need to new board[m * n + 1]
if((i == 0 || i == m - 1 || j == 0 || j == n - 1) && board[i][j] == 'O') {
uf.union(i * n + j, m * n);
}
else if(board[i][j] == 'O') // connect a 'O' node to its neighbour 'O' nodes
{
if(board[i - 1][j] == 'O') {
uf.union(i * n + j, (i - 1) * n + j);
}
if(board[i + 1][j] == 'O') {
uf.union(i * n + j, (i + 1) * n + j);
}
if(board[i][j - 1] == 'O') {
uf.union(i * n + j, i * n + j - 1);
}
if(board[i][j + 1] == 'O') {
uf.union(i * n + j, i * n + j + 1);
}
}
}
}
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(!uf.connected(i * n + j, m * n)){ // if a 'O' node is not connected to the dummy node, it is captured
board[i][j] = 'X';
}
}
}
}
}
