wayetan
2/19/2014 - 10:20 AM

Surrounded Regions

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
 */
public class Solution {
    private Queue<Integer> queue = new LinkedList<Integer>();
    public void solve(char[][] board) {
        if(board == null || board.length == 0)
            return;
        int row = board.length, col = board[0].length;
        for(int i = 0; i < row; i++) {
            if(board[i][0] == 'O') {
                bfs(board, i, 0);
            }
            if(board[i][col - 1] == 'O'){
                bfs(board, i, col - 1);
            }
        }
        for(int i = 0; i < col; i++) {
            if(board[0][i] == 'O') {
                bfs(board, 0, i);
            }
            if(board[row - 1][i] == 'O') {
                bfs(board, row - 1, i);
            }
        }
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
                if(board[i][j] == 'P') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    private void bfs(char[][] board, int i, int j) {
        int col = board[0].length;
        fill(board, i, j);
        while(!queue.isEmpty()) {
            int cur = queue.poll();
            int x = cur / col;
            int y = cur % col;
            fill(board, x - 1, y);
            fill(board, x + 1, y);
            fill(board, x, y + 1);
            fill(board, x, y - 1);
        }
    }
    private void fill(char[][] board, int i, int j) {
        int row = board.length;
        int col = board[0].length;
        if(i < 0 || i >= row || j < 0 || j >= col || board[i][j] != 'O')
            return;
        queue.offer(i * col + j);
        board[i][j] = 'P';
    }
    
    // an easier way to program this
    public void solve(char[][] board) {
        if(board.length == 0) return;
        for(int i = 0; i < board[0].length; i++){
            helper(board, 0 , i);
        }
        for(int i = 1; i < board.length; i++) {
            helper(board, i, board[0].length - 1);
        }
        for(int i = 0; i < board[0].length - 1; i++) {
            helper(board, board.length - 1, i);
        }
        for(int i = 1; i < board.length - 1; i++) {
            helper(board, i, 0);
        }
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                board[i][j] = (board[i][j] == 'M') ? 'O' : 'X';
            }
        }
        return;
    }
    public void helper(char[][] board, int a, int b) {
        if(board[a][b] == 'X' || board[a][b] == 'M')  return;
        board[a][b] = 'M'; // mark as visited
        if(a + 1 < board.length)    helper(board, a + 1, b);
        if(a - 1 > 0)   helper(board, a - 1, b);
        if(b + 1 < board[0].length)     helper(board, a, b + 1);
        if(b - 1 > 0)   helper(board, a, b - 1);
    }
}