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)
思路：找边界联通的所有的0，置为*。然后0置为X，*置为0
a最好在递归前就check是否visited或出界，如果没有，再递归去visit
b或是写法简单的：直接dfs，但每次进入递归再检查是否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)

思路：找联通的所有的0，置为*。然后0置为X，*置为1
在放入stack前就check是否visited，如果没有visit过，再放入stack
Time Complexity: O(mn) Space Complexity: O(mn)

Solution3：边界BFS (queue)

思路：找联通的所有的0，置为*。然后0置为X，*置为1
在放入queue前就check是否visited，如果没有visit过，再放入queue
Time Complexity: O(mn) Space Complexity: O(mn)

Solution4：Union Find

思路：每个位置的元素初始都assigned 一个id，并多建一个id[mn]作为边缘标志。遍历将所有的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';
                }
            }
        }
    }
    
    
}