[LeetCode] - Surrounded Regions

Given a 2D board containing 

'X'

 and 

'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      

這個題目的思路分兩步：

1. 把棋盤四周的"O"以及與其直接相連的“O”全部都變為“Q”，因為這種“O”是“X”圍不住的。這裡采用BFS算法。BFS我習慣的寫法就是MIT算法課裡面講的，frontier加next進行while循環。要注意的是，把點放到frontier和next之前就要改變其狀态，要不然會有重複的點被加進去。

2. 經過第一步之後，棋盤中還剩下的“O”就是可以被“X”圍住的。是以接下來就要将“O”變為“X”，然後将“Q“變為”O“。這裡要注意先後順序，要不然第一步就白忙活了，又都變回去了。

代碼如下：

public class Solution {
    public void solve(char[][] board) {
        if(board==null || board.length==0 || board[0].length==0) return;
        flipOToQ(board);
        flipOToX(board);
        return;
    }
    
    public void flipOToQ(char[][] board) {
        for(int i=0; i<board[0].length; i++) {
            if(board[0][i] == 'O') {
                flipOToQHelper(board, 0, i);
            }
            if(board[board.length-1][i] == 'O') {
                flipOToQHelper(board, board.length-1, i);
            }
        }
        for(int j=0; j<board.length; j++) {
            if(board[j][0] == 'O') {
                flipOToQHelper(board, j, 0);
            }
            if(board[j][board[0].length-1] == 'O') {
                flipOToQHelper(board, j, board[0].length-1);
            }
        }
        return;
    }
    
    // BFS, change state before adding into frontier and next
    public void flipOToQHelper(char[][] board, int row, int col) {
        Queue<Position> frontier = new LinkedList<Position>();
        frontier.add(new Position(row, col));
        board[row][col] = 'Q';
        while(!frontier.isEmpty()) {
            Queue<Position> next = new LinkedList<Position>();
            while(!frontier.isEmpty()) {
                Position temp = frontier.poll();
                if(temp.col-1>=0 && board[temp.row][temp.col-1]=='O') {
                    board[temp.row][temp.col-1] = 'Q';
                    next.add(new Position(temp.row, temp.col-1));
                }
                if(temp.col+1<board[0].length && board[temp.row][temp.col+1]=='O') {
                    board[temp.row][temp.col+1] = 'Q';
                    next.add(new Position(temp.row, temp.col+1));
                }
                if(temp.row-1>=0 && board[temp.row-1][temp.col]=='O') {
                    board[temp.row-1][temp.col] = 'Q';
                    next.add(new Position(temp.row-1, temp.col));
                }
                if(temp.row+1<board.length && board[temp.row+1][temp.col]=='O') {
                    board[temp.row+1][temp.col] = 'Q';
                    next.add(new Position(temp.row+1, temp.col));
                }
            }
            frontier = next;
        }
        return;
    }
    
    public void flipOToX(char[][] board) {
        for(int i=0; i<board.length; i++) {
            for(int j=0; j<board[0].length; j++) {
                if(board[i][j]=='O') board[i][j]='X';
                if(board[i][j]=='Q') board[i][j]='O';
            }
        }
        return;
    }
}

class Position {
    public int row;
    public int col;
    public Position(int r, int c) {
        this.row = r;
        this.col = c;
    }
}