130. Surrounded Regions

Problem:

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

Analysis:

一开始的想法是，把所有的O找到。然后BFS，剔除边界O，结果超时了。

Find the O on the edge. BFS from those Os. Mark the adjacent to '+'. Then mark other Os to 'X' and mark '+' back to O.

BFS不能死脑经蛮干，不然效率会很低。

Solution:

class Solution {
    public void solve(char[][] board) {
        int[] dx = new int[]{0, 0, 1, -1};
        int[] dy = new int[]{1, -1, 0, 0};
        if (board == null || board.length == 0) return;
        int m = board.length;
        int n = board[0].length;
        
        Queue<Integer> queue = new LinkedList<>();
        
        for (int i = 0; i < n; i++) {
            if (board[0][i] == 'O') {
                board[0][i] = '+';
                queue.offer(i);
            }
           
            if (board[m - 1][i] =='O') {
                board[m - 1][i] = '+';
                queue.offer((m - 1)*n + i);
            }
        }

         for (int i = 0; i < m; i++) {

            if (board[i][0] == 'O') {
                board[i][0] = '+';
                queue.offer(i*n);
            }

            if (board[i][n - 1] == 'O') {
                board[i][n - 1] = '+';
                queue.offer(i*n + n - 1);
            }
        }
        
        while(!queue.isEmpty()) {
             int cur = queue.poll();
             int x = cur / n;
             int y = cur % n;
             for (int q = 0; q < 4; q++) {
                 int newx = x + dx[q];
                 int newy = y + dy[q];
                 int newIndex = newx*n + newy;
                 if (newx < 0 || newx >= m || newy < 0 || newy >= n || board[newx][newy] != 'O') {
                     continue;
                 }
                 board[newx][newy] = '+';
                 queue.offer(newIndex);
            }
        }
        
        for (int i = 0; i < m; i++) 
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') 
                    board[i][j] = 'X';
                if (board[i][j] == '+')
                    board[i][j] = 'O';
            }
        return;
    }
}