Question:

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.

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

Explanation: Surrounded regions shouldn’t be on the border, which means that any ‘O’ on the border of the board are not flipped to ‘X’. Any ‘O’ that is not on the border and it is not connected to an ‘O’ on the border will be flipped to ‘X’. Two cells are connected if they are adjacent cells connected horizontally or vertically.

Thinking:

  • Method1:
    • 只有与最外圈的O相连接的结点无法被转换。
    • 如果最外层为O，我们通过BFS，不断获取与之相邻的O结点。
class Solution {
    public void solve(char[][] board) {
        if(board == null || board.length <= 2 || board[0].length <= 2) return;
        int height = board.length;
        int width = board[0].length;
        //row
        for(int i = 0; i < width; i++){
            if(board[0][i] == 'O')
                fill(board, 0, i);
            if(board[height - 1][i] == 'O')
                fill(board, height - 1, i);
        }
        //col
        for(int i = 0; i < height; i++){
            if(board[i][0] == 'O')
                fill(board, i, 0);
            if(board[i][width - 1] == 'O')
                fill(board, i, width - 1);
        }
        for(int i = 0; i < height; i++){
            for(int j = 0; j < width; j++){
                if(board[i][j] == 'O') board[i][j] = 'X';
                else if(board[i][j] == '#') board[i][j] = 'O';
            }
        }
    }
    private static void fill(char[][] board, int row, int col){
        LinkedList<Integer> q = new LinkedList<>();
        int width = board[0].length;
        board[row][col] = '#';
        q.add(row * width + col);
        while(!q.isEmpty()){
            Integer n = q.poll();
            int x = n / width;
            int y = n % width;
            if(x > 0) if(board[x - 1][y] == 'O'){board[x - 1][y] = '#'; q.add((x - 1) * width + y);}
            if(y > 0) if(board[x][y - 1] == 'O'){board[x][y - 1] = '#'; q.add(x * width + y - 1);}
            if(x < board.length - 1) if(board[x + 1][y] == 'O'){board[x + 1][y] = '#'; q.add((x + 1) * width + y);}
            if(y < board[0].length - 1) if(board[x][y + 1] == 'O'){board[x][y + 1] = '#'; q.add(x * width + y + 1);}
        }
    }
}

二刷

  1. 还是和一刷的思路一样，就是从周围开始扩张，通过DFS找到与之相邻的O，这些O是无法转化的，剩下的O则是可以转化成X的O。
  2. 需要用一个中间变量字符作为存储，不然会影响到后续的判断。 
    class Solution {
 public void solve(char[][] board) {
     if(board == null || board.length == 0 || board[0].length == 0) return;
     int height = board.length, width = board[0].length;
     for(int i = 0; i < height; i++){
         if(board[i][0] == 'O') fill(board, i, 0);
         if(board[i][width - 1] == 'O') fill(board, i, width - 1);
     }
     for(int i = 0; i < width; i++){
         if(board[0][i] == 'O') fill(board, 0, i);
         if(board[height - 1][i] == 'O') fill(board, height - 1, i);
     }
     for(int i = 0; i < height; i++){
         for(int j = 0; j < width; j++){
             if(board[i][j] == 'O') board[i][j] = 'X';
             else if(board[i][j] == 'Z') board[i][j] = 'O';
         }
     }
 }
 private void fill(char[][] board, int row, int col){
     board[row][col] = 'Z';
     int tempRow = 0, tempCol = 0;
     int height = board.length, width = board[0].length;
     for(int i = 0; i < 4; i++){
         tempRow = row + dir[i][0];
         tempCol = col + dir[i][1];
         if(tempRow >= 0 && tempRow < height && tempCol >= 0 && tempCol < width && board[tempRow][tempCol] == 'O')
             fill(board, tempRow, tempCol);
     }
 }
}