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

思路：这个题和number of islands差不多。也用到flood fill的思想。想不起来可以看看number of island那个日志。我们先把靠边的O都标记成一个别的字符比如N。然后剩下的O就是被X包围的。

扫描一遍board，把剩下的O标记为X。标记为别的字符的地方还原为O。

一开始用dfs的foolfill。结果超时了(修改：不是超时，是stack overflow)。。。所以改写成BFS的。思路一样。这样就能通过了。

    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return;
        }
        int rowLen = board.length; //1
        int colLen = board[0].length; // 1
        for (int i = 0; i < rowLen; i++) {
            if (board[i][0] == 'O') {
                floodfill('N', i, 0, board);
            }
            if (board[i][colLen - 1] == 'O') {
                floodfill('N', i, colLen - 1, board);
            }
        }
        for (int j = 0; j < colLen; j++) {
            if (board[0][j] == 'O') {
                floodfill('N', 0, j, board);
            }
            if (board[rowLen - 1][j] == 'O') {
                floodfill('N', rowLen - 1, j, board);
            }
        }
        
        for (int i = 0; i < rowLen; i++) {
            for (int j = 0; j < colLen; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
                if (board[i][j] == 'N') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    /*
    public void floodfill(char c, int i, int j, char[][] board) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != 'O') {
            return;
        }else{
            board[i][j] = c;
        }
        floodfill(c, i + 1, j, board);
        floodfill(c, i - 1, j, board);
        floodfill(c, i, j + 1, board);
        floodfill(c, i, j - 1, board);
    }
    */
    private static void floodfill(char c, int i, int j, char[][] board) {
        Queue<Integer> q = new LinkedList<Integer>();
        int rowLen = board.length;
        int colLen = board[0].length;
        board[i][j] = c;
        q.offer(i * colLen + j);
        while (!q.isEmpty()) {
            int index = q.poll();
            int row = index / colLen;
            int col = index % colLen;
            if (row - 1 > 0 && board[row - 1][col] == 'O') {
                board[row - 1][col] = c;
                q.offer((row - 1) * colLen + col);
            }
            if (row + 1 < rowLen && board[row + 1][col] == 'O') {
                board[row + 1][col] = c;
                q.offer((row + 1) * colLen + col);
            }
            if (col - 1 > 0 && board[row][col - 1] == 'O') {
                board[row][col - 1] = c;
                q.offer(row * colLen + col - 1);
            }
            if (col + 1 < colLen && board[row][col + 1] == 'O') {
                board[row][col + 1] = c;
                q.offer(row* colLen + col + 1);
            }
        }
    }