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

解题思路：

board的四个边上的O是无法被X包围的，故如果在四个边上发现O，则这些O应当被保留 从这些O出发继续寻找相邻的O，这些O也是要保留的

等这些O都标记结束，则剩余的O就应该被改成X

private static Queue<Integer> queue = null;
private static char[][] board;
private static int rows = 0;
private static int cols = 0;

public void solve(char[][] board) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if (board.length == 0 || board[0].length == 0) return;
        queue = new LinkedList<Integer>();
        board = board;
        rows = board.length;
        cols = board[0].length;

        //第一行和最后一行
        for (int i = 0; i < rows; i++) {
            enqueue(i, 0);
            enqueue(i, cols - 1);
        }

        //第一列和最后一列
        for (int j = 1; j < cols - 1; j++) { // **important**
            enqueue(0, j);
            enqueue(rows - 1, j);
        }

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            int x = cur / cols,
                y = cur % cols;

            if (board[x][y] == 'O') {
                board[x][y] = 'D';
            }

            enqueue(x - 1, y);
            enqueue(x + 1, y);
            enqueue(x, y - 1);
            enqueue(x, y + 1);
        }

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == 'D') board[i][j] = 'O';
                else if (board[i][j] == 'O') board[i][j] = 'X';
            }
        }

        queue = null;
        board = null;
        rows = 0;
        cols = 0;
}

public static void enqueue(int x, int y) {
    if (x >= 0 && x < rows && y >= 0 && y < cols && board[x][y] == 'O'){  
        queue.offer(x * cols + y);
    }
}