Surrounded Regions 477

Question

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.

Example

X X X X

X O O X

X X O X

X O X X

After capture all regions surrounded by 'X', the board should be:

X X X X

X X X X

X X X X

X O X X

Solution

board中的'O'只能属于两类：1）边界的'O'（没有被'X'完全包围）；2）内部的'O'（被'X'完全包围）。因此，只要搜索board上下左右四条边界，找出所有边界'O'的union中的所有点，将其标为'F'，则board中剩下的'O'必然属于surround region。

代码如下：

public class Solution {
    /**
     * @param board a 2D board containing 'X' and 'O'
     * @return void
     */
    //搜索board上下左右四个边界，找到其边界上'O'的union，将其标为'F'，则board中剩下的'O'必然属于surround region
    //上下左右搜索
    static final int[] dx = {-1, 1, 0, 0};
    static final int[] dy = {0, 0, -1, 1};
    //用F表明和边界'O'相连的'O'，用'V'表明访问过的点
    static final char Free = 'F';
    static final char Visited = 'V';

    class Node{
        int x;
        int y;
        public Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    public void surroundedRegions(char[][] board) {
        // Write your code here
        if(board == null || board.length == 0 || board[0].length == 0){
            return;
        }

        int row = board.length;
        int col = board[0].length;
        //找出左右边界上'O'的union，并将其都替换为'F'
        for(int i = 0; i < row; i++){
            bfs(board, i, 0);
            bfs(board, i, col - 1);
        }
        //找出上下边界上'O'的union，并将其都替换为'F'
        for(int j = 1; j < col - 1; j++){
            bfs(board, 0, j);
            bfs(board, row - 1, j);
        }
        //遍历整个board，所有标记为'F'的点都属于边界上的'O'的union，将其都变回原来的值；所有标记仍为'O'的点都属于surrounded regions，将其都变为'X'
        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] == 'F'){
                    board[i][j] = 'O';
                }
            }
        }
    }

    private void bfs(char[][] board, int x, int y){
        if(board[x][y] == 'X'){
            return;
        }
        //用bfs算法搜索所有边界上'O'的union的所有点并入列，在出列时将其变为'F'，以表示该点属于边界上'O'的union
        Queue<Node> queue = new LinkedList<Node>();
        queue.offer(new Node(x, y));

        while(!queue.isEmpty()){
            Node curt = queue.poll();
            board[curt.x][curt.y] = Free;

            for(Node node : expand(board, curt.x, curt.y)){
                queue.offer(node);
            }
        }
    }
    //搜索当前点四周的点，返回合法的点的list
    private ArrayList<Node> expand(char[][] board, int x, int y){
        ArrayList<Node> expansion = new ArrayList<Node>();

        for(int i = 0; i < dx.length; i++){
            int curtX = x + dx[i];
            int curtY = y + dy[i];
            //当其周围的点不越界，同时为'O'时，入列
            if(curtX >= 0 && curtY >= 0 && curtX < board.length && curtY < board[0].length && (board[curtX][curtY] == 'O')){
                //将入列的点标记为'V'，这样可以保证之后不会重复入列
                board[curtX][curtY] = Visited;
                expansion.add(new Node(curtX, curtY));
            }
        }

        return expansion;
    }
}