class Solution {
    //BFS
    //定义方向
    public static final List<int[]> DIRECTIONS = Arrays.asList(
        new int[]{1, 0},
        new int[]{-1, 0},
        new int[]{0, 1},
        new int[]{0, -1}
    );

    public void solve(char[][] board) {
        //https://leetcode-cn.com/problems/surrounded-regions/solution/bei-wei-rao-de-qu-yu-by-leetcode-solution/
        int row = board.length;
        //corner case
        if(row == 0) return;
        int col = board[0].length;

        Queue<int[]> q = new LinkedList<>();

        //遍历上边下边，遇到O，入队等待BFS处理
        for(int i = 0; i < col; i++){
            if(board[0][i] == 'O') q.add(new int[]{0, i});
            if(board[row - 1][i] == 'O') q.add(new int[]{row - 1, i});
        }

        //遍历上边下边，遇到O，入队等待BFS处理
        for(int i = 0; i < row; i++){
            if(board[i][0] == 'O') q.add(new int[]{i, 0});
            if(board[i][col - 1] == 'O') q.add(new int[]{i, col - 1});
        }

        //队列处理BFS
        while(!q.isEmpty()){
            int[] position = q.poll();
            int r = position[0];
            int c = position[1];
            //将该位置上的O置为A
            board[r][c] = 'A';
            //向四个方向处理
            for(int[] direction: DIRECTIONS){
                int nextR = r + direction[0];
                int nextC = c + direction[1];
                //判断边界条件
                if(nextR < 0 || nextR >= board.length || nextC < 0 || nextC >= board[0].length || board[nextR][nextC] != 'O' ) continue;
                //入队
                q.add(new int[]{nextR, nextC});
            }

        }

        //遍历整个数组，将所有O变成X，将所有A变成O
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(board[i][j] == 'O') board[i][j] = 'X';
                else if(board[i][j] == 'A') board[i][j] = 'O';
            }
        }
    }

//     //DFS
//     public void solve(char[][] board) {
//         //ans：https://leetcode-cn.com/problems/surrounded-regions/solution/bei-wei-rao-de-qu-yu-by-leetcode-solution/
//         int row = board.length;
//         //corner case
//         if(row == 0) return;
//         int col = board[0].length;
//         //遍历上边和下边，遇到0就dfs，置为A
//         for(int i = 0; i < col; i++){
//             if(board[0][i] == 'O') dfs(0, i, board);
//             if(board[row - 1][i] == 'O') dfs(row - 1, i, board);
//         }

//         //遍历左边和右边，遇到0就dfs，置为A
//         for(int i = 0; i < row; i++){
//             if(board[i][0] == 'O') dfs(i, 0, board);
//             if(board[i][col - 1] == 'O') dfs(i, col - 1, board);
//         }

//         //遍历整个数组，遇到0，就置为X；遇到A，就置为0
//         for(int i = 0;i < row; i++){
//             for(int j = 0; j < col; j++){
//                 if(board[i][j] == 'O') board[i][j] = 'X';
//                 else if(board[i][j] == 'A') board[i][j] = 'O';
//             }
//         }
//     }

//     public void dfs(int r, int c, char[][] board){
//         //递归退出条件
//         if(r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != 'O') return;
//         //将0置为A
//         board[r][c] = 'A';
//         //深度优先
//         dfs(r + 1, c, board);
//         dfs(r - 1, c, board);
//         dfs(r, c + 1, board);
//         dfs(r, c - 1, board);
//     }
}