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

Solution: BFS.把与边界相连的‘O'改为'K'，最后把'O'改为'X', 'K'改为'O'

    int[] dx = {1, 0, -1, 0};
    int[] dy = {0, 1, 0, -1};
    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        int m = board.length, n = board[0].length;

        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {                
                bfs(queue, board, i, 0);
            }
            if (board[i][n - 1] == 'O') {                
                bfs(queue, board, i, n - 1);
            }
        }
        for (int i = 1; i < n - 1; i++) {
            if (board[0][i] == 'O') {                
                bfs(queue, board, 0, i);
            }
            if (board[m - 1][i] == 'O') {                
                bfs(queue, board, m - 1, i);
            }
        }
        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] == 'K') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    private void bfs(Queue<Node> queue, char[][] board, int m, int n) {
        queue.offer(new Node(m, n));
        board[m][n] = 'K';
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            for (int i = 0; i < 4; i++) {
                int x = cur.x + dx[i], y = cur.y + dy[i];
                if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] != 'O') {
                    continue;
                }
                queue.offer(new Node(x, y));
                board[x][y] = 'K';
            }
        }
    }
    class Node {
        int x, y;
        public Node(int i, int j) {
            x = i;
            y = j;
        }
    }