首页 > 代码库 > 【LeetCode】Surrounded Regions 解题报告

【LeetCode】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


【DFS】

参考:http://blog.csdn.net/ojshilu/article/details/22600449#reply

两点:

1、从边缘入手,因为和边缘上的‘O’相连的‘O’都不会变,所以找出所有这样的‘O’,剩下的‘O’就是被完全包围的,把它们全部变为‘X’。

2、DFS过程中,暂时把遍历过的‘O‘用另外一个符号’#‘代替,最后把被包围的’O‘变成’X‘后,在把‘#’恢复成‘O’。

public class Solution {
    public void solve(char[][] board) {
        int row = board.length;
        if (row < 3) return;
        int col = board[0].length;
        if (col < 3) return;
        
        // first column and last column
        for (int i = 0; i < row; i++) {
            if (board[i][0] == 'O') {
                board[i][0] = '#';
                dfs(board, i, 0);
            }
            if (board[i][col - 1] == 'O') {
                board[i][col - 1] = '#';
                dfs(board, i, col - 1);
            }
        }
        
        // first row and last row
        for (int j = 0; j < col; j++) {
            if (board[0][j] == 'O') {
                board[0][j] = '#';
                dfs(board, 0, j);
            }
            if (board[row - 1][j] == 'O') {
                board[row - 1][j] = '#';
                dfs(board, row - 1, j);
            }
        }
        
        // change 'O' to 'X', restore '#' to 'O'
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    
    public void dfs(char[][] board, int i, int j) {
        int row = board.length;
        int col = board[0].length;
        
        // up
        if (i > 1 && board[i - 1][j] == 'O') {
            board[i - 1][j] = '#';
            dfs(board, i - 1, j);
        }
        // below
        if (i < row - 2 && board[i + 1][j] == 'O') {
            board[i + 1][j] = '#';
            dfs(board, i + 1, j);
        }
        // left
        if (j > 1 && board[i][j - 1] == 'O') {
            board[i][j - 1] = '#';
            dfs(board, i, j - 1);
        }
        // right
        if (j < col - 2 && board[i][j + 1] == 'O') {
            board[i][j + 1] = '#';
            dfs(board, i, j + 1);
        }
    }
}

注意,当行或列少于3时,不可能有被包围的‘O’。

这种思路简单易于理解,代码也很整洁,很适合初学者理解。

这个思路是从边缘向内部找连通的‘O’的,所以DFS时,就没必要在判断边缘上的字母了,因此DFS中,i 和 j 的条件为:i > 1, i < row - 2; j > 1, j < col - 2。(为什么?如果是 i = 1 时,那么 dfs(board, i - 1, j) 就是判断 [0, j] 了,而而边缘上的字母会被遍历判断的,这样就重复判断了,会导致栈溢出)。

DFS递归太深,容易栈溢出,这个代码可谓险过,最好还是用BFS。


【BFS】

参考:http://blog.sina.com.cn/s/blog_b9285de20101j1dt.html

public class Solution {
    char[][] board;
    int row;
    int col;
    Queue<Integer> queue = new LinkedList<Integer>();
    
    public void solve(char[][] board) {
        this.board = board;
        row = board.length;
        if (row < 3) return;
        col = board[0].length;
        if (col < 3) return;
        
        // traverse first column and last column
        for (int i = 0; i < row; i++) {
            bfs(i, 0);
            bfs(i, col - 1);
        }
        
        // traverse first row and last row
        for (int j = 0; j < col; j++) {
            bfs(0, j);
            bfs(row - 1, j);
        }
        
        // change 'O' to 'X', restore '#' to 'O'
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    
    public void bfs(int i, int j) {
        fill(i, j);
        while (!queue.isEmpty()) {
            int pos = queue.poll();
            int x = pos / col;
            int y = pos % col;
            
            fill(x - 1, y);
            fill(x + 1, y);
            fill(x, y - 1);
            fill(x, y + 1);
        }
    }
    
    public void fill(int i, int j) {
        if (i < 0 || j < 0 || i > row - 1 || j > col - 1) return;
        if (board[i][j] != 'O') return;
        queue.offer(i * col + j);
        board[i][j] = '#';
    }
}

DFS的实现是函数递归,BFS的实现是利用一个Queue。

关键的一点是,把 [i, j] 转化为 i * col + j 存储到Queue<Integer>里。


【LeetCode】Surrounded Regions 解题报告