Leetcode(130) Surrounded Regions

发表于 | 分类于

Description

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.

Example:

1
2
3
4
X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

1
2
3
4
X X X X
X X X X
X X X X
X O X X

Explanation:

Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

解法

如果直接从一个’O’开始搜索判断是不是会到达边界，将会非常麻烦，因为需要保存路径上的每个’O’，如果到达边界就放弃这片区域的所有值，否则将其变为’X’。有一种更为聪明的做法是从四个边界出发，用DFS算法将从边界开始的’O’的区域都变成另外一个临时的值，这样做完之后剩下的‘O’将会是被包围的，然后将其变为‘X’，再将临时的值变为’O’即可。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    public void solve(char[][] board) {
        if(board.length == 0){
            return;
        }
        int m = board.length;
        int n = board[0].length;
        for(int i = 0; i < m; i++){
            if(board[i][0] == 'O'){
                dfsHelper(board, i ,0);
            }
        }
        for(int i = 0; i < m; i++){
            if(board[i][n-1] == 'O'){
                dfsHelper(board, i , n-1);
            }
        }        
        for(int j = 0; j < n; j++){
            if(board[0][j] == 'O'){
                dfsHelper(board, 0 ,j);
            }
        }
        for(int j = 0; j < n; j++){
            if(board[m-1][j] == 'O'){
                dfsHelper(board, m-1 ,j);                
            }
        }
        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';
                }
            }
        }
    }
    void dfsHelper(char[][] board, int x, int y){
        board[x][y] = '#';
        int[] nextX = {0,0,-1,1};
        int[] nextY = {1,-1,0,0};
        for(int i = 0; i < 4; i++){
            int newX = x + nextX[i];
            int newY = y + nextY[i];
            if(newX >= 0 && newX < board.length && newY >= 0 && newY < board[0].length){
                if(board[newX][newY] == 'O'){
                    dfsHelper(board, newX, newY);
                }
            }
        }
    }
}