Given a 2D board containing'X'and'O'(theletterO), 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

tag: BFS

class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;

        int n = board.length, m = board[0].length;
        Queue<int[]> q = new LinkedList<>();
        for (int j = 0; j < m; j++){
            if (board[0][j] == 'O') q.offer(new int[]{0, j});
            if (board[n - 1][j] == 'O') q.offer(new int[]{n - 1, j});
        }
        for (int i = 1; i < n - 1; i++){
            if (board[i][0] == 'O') q.offer(new int[]{i, 0});
            if (board[i][m - 1] == 'O') q.offer(new int[]{i, m - 1});
        }

        int[][] moves = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        while (!q.isEmpty()){
            int[] cur = q.poll();
            int x = cur[0];
            int y = cur[1];
            board[x][y] = 'A';

            for (int i = 0; i < 4; i++){
                int xx = x + moves[i][0];
                int yy = y + moves[i][1];

                if (xx < 0 || xx >= n || yy < 0 || yy >= m || board[xx][yy] != 'O') continue;

                q.offer(new int[]{xx, yy});
            }
        }

        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (board[i][j] != 'A'){
                    board[i][j] = 'X';
                }
            }
        }

        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (board[i][j] == 'A'){
                    board[i][j] = 'O';
                }
            }
        }
    }
}