首页 > itarticle > leetcode 130 surrounded regions

leetcode 130 surrounded regions

admin 11月 14, 2020 0

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.

可以反过来思考，所有从board四周延伸出来的O都应该保持不变，除此之外的O都要转换为X。

这样一来，先把所有四周延伸出来的O都值为一个其他值，例如*。

然后遍历一遍board，将所有的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
 
class  {
    public void solve(char[][] board) {
        if (board.length == 0 || board[0].length == 0) return ;
        int m = board.length;
        int n = board[0].length;
        for (int i=0; i<m; i++) {
            if (board[i][0] == 'O')
                covert(board, i, 0);
            if (board[i][n-1] == 'O')
                covert(board, i, n-1);
        }
        for (int j=0; j<n; j++) {
            if (board[0][j] == 'O')
                covert(board, 0, j);
            if (board[m-1][j] == 'O')
                covert(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';
            }
        }
    }
    
    public void covert(char[][] board, int i, int j) {
        board[i][j] = '*';
        if (i-1>=0 && board[i-1][j] == 'O')
            covert(board, i-1, j);
        if (i+1 < board.length && board[i+1][j] == 'O')
            covert(board, i+1, j);
        if (j-1 >= 0 && board[i][j-1] == 'O')
            covert(board, i, j-1);
        if (j+1 < board[0].length && board[i][j+1] == 'O')
            covert(board, i, j+1);
    }
}

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能