130. Surrounded Regions

题目分析

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

代码

解法一：广度优先搜索（BFS）

class Solution {
    public void solve(char[][] board) {
        if(board == null || board.length < 3) {
            return;
        }
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[i].length; j++) {
                // 判断是不是边缘并且边缘上的点为 O
                if((i == 0 || j == 0 || i == board.length - 1 || j == board[i].length - 1) && (board[i][j] == 'O')) {
                    Queue<Integer> q = new LinkedList<Integer>();
                    q.offer(i * board[i].length + j);
                    board[i][j] = 'A';
                    while(!q.isEmpty()) {
                        Integer key = q.poll();
                        // 计算出在第 x 行，第 y 列
                        int x = key / board[i].length;
                        int y = key % board[i].length;
                        // 同一列的，上一行位置是不是 O，同时用 x > 0，判断是不是最上面的那一行
                        if(x > 0 && board[x - 1][y] == 'O') {
                            // 如果是，该位置入队列
                            q.offer((x - 1) * board[i].length + y);
                            board[x - 1][y] = 'A';
                        }
                        if(x < board.length - 1 && board[x + 1][y] == 'O') {
                            // 如果是，该位置入队列
                            q.offer((x + 1) * board[i].length + y);
                            board[x + 1][y] = 'A';
                        }
                        // 同一行的左边是不是 O
                        if(y > 0 && board[x][y - 1] == 'O') {
                            q.offer(x * board[i].length + y - 1);
                            board[x][y - 1] = 'A';
                        }
                        // 同一行的右边是不是 O
                        if(y < board[i].length - 1 && board[x][y + 1] == 'O') {
                            q.offer(x * board[i].length + y + 1);
                            board[x][y + 1] = 'A';
                        }
                        
                    }
                }
            }
        }
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[i].length; j++) {
                if(board[i][j] == 'O') board[i][j] = 'X';
                if(board[i][j] == 'A') board[i][j] = 'O';
            }
        }
    }
}

解法二：深度优先搜索（DFS）
参考