Haiyang Yu's Blog
0%

Leetcode 130 Surrounded Regions

发表于 更新于 分类于 Valine：
本文字数： 1.7k 阅读时长 ≈ 2 分钟

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.

BFS

关键是读懂题意. 这题读懂题意之后就很好做了

对于内部的一个点’O’, 我们判断某个这个块是否到达边界是不好判定的.

但是可以从边界开始找, 找到四周边界上所有O组成的块, 将他们置为P, 然后遍历二维数组, O变为X, P变为O.

1
2
3
4
X X X X
X O O X
X X O X
X O X X
1
2
3
4
X X X X
X O O X
X X O X
X P X X
1
2
3
4
X X X X
X X X X
X X X X
X O X X
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
class Solution {
    public void solve(char[][] board) {
        if(board == null || board.length == 0)
            return;
        final int M = board.length;
        final int N = board[0].length;
        for(int j = 0; j < N; ++j)
        {
            setOtoP(board, 0, j);
            setOtoP(board, M - 1, j);
        }
        for(int i = 0; i < M; ++i)
        {
            setOtoP(board, i, 0);
            setOtoP(board, i, N - 1);
        }
        
        for(int i = 0; i < M; ++i)
        {
            for(int j = 0; j < N; ++j)
            {
                if(board[i][j] == 'O')
                    board[i][j] = 'X';
                else if(board[i][j] == 'P')
                    board[i][j] = 'O';
            }
        }
        
    }
    
    private void setOtoP(char[][] board, int i , int j)
    {
        if(isLocationValid(board, i, j) && board[i][j] == 'O')
        {
            board[i][j] = 'P';
            setOtoP(board, i + 1, j);
            setOtoP(board, i - 1, j);
            setOtoP(board, i, j + 1);
            setOtoP(board, i, j - 1);
        }
    }
    
    private boolean isLocationValid(char[][] board, int i, int j)
    {
        int M = board.length;
        int N = board[0].length;
        return i > -1 && i < M && j > -1 && j < N;
    }
}