leetcode130.Surrounded Regions

发表于 更新于 分类于 ，

题目要求

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

将所有被X环绕的O区域获取出来并转化为X

思路与代码

这篇题目与leetcode200. Number of Islands思路非常相近，建议毫无思路的同学先参考一下这篇博客。其实这种将区域相连的题目往往都可以使用深度优先遍历或者是Union-Find方法来实现。在这里我就给出深度优先遍历的实现方法，有兴趣的同学可以参考上文的博客来自己实现Union-Find方法。

和leetcode200题不同，在本题中，只有被完全包围的图形才可以被选中与转化，也就是，任何一个和数组边界上的O相连的都不可能是完全包围。所以在这题里我们采用逆向思维。将所有和边界O相连的O都标记出来。那么当我重新遍历数组的时候，剩下的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
public void solve(char[][] board) {
    if(board.length<=2 || board[0].length<=2 ) return;
    int row = board.length;
    int column = board[0].length;
    for(int i = 0 ; i<row ; i++){
        if(board[i][0] == 'O'){
            boundarySearch(board,i,0);
        }
        if(board[i][column-1]=='O'){
            boundarySearch(board, i, column-1);
        }
    }
    for(int j = 0 ; j<column ; j++){
        if(board[0][j] == 'O'){
            boundarySearch(board, 0, j);
        }
        if(board[row-1][j] == 'O'){
            boundarySearch(board, row-1, j);
        }
    }
    
    for(int i = 0 ; i<row ; i++){
        for(int j = 0 ; j<column ; j++){
            if(board[i][j]=='O'){
                board[i][j] = 'X';
            }else if(board[i][j]=='*'){
                board[i][j] = 'O';
            }
        }
    }
}

public void boundarySearch(char[][] board, int i, int j){
    if(i<0 || j<0 || i>=board.length || j>=board[0].length) return;
    if(board[i][j] == 'X' || board[i][j]=='*') return;
    board[i][j] = '*';
    if(i>1 && board[i-1][j]=='O') boundarySearch(board, i-1, j);
    if(j>1 && board[i][j-1]=='O') boundarySearch(board, i, j-1);
    if(i<board.length-2 && board[i+1][j]=='O') boundarySearch(board, i+1, j);
    if(j<board[0].length-2 && board[i][j+1]=='O') boundarySearch(board, i, j+1);
    
}