LeetCode: 130. Surrounded Regions

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

130. Surrounded Regions

LeetCode - Surrounded Regions

这道题的关键点在于找到入口。对我们来说，入口就是边界的的 O，然后与之相连的 O，其他的 O 都会被替换为 X。为了区别对待，可以把识别出来的 O 替换为其他的字符，比如 #。这样后期再遍历处理即可。

思考题：看题解可以使用 UnionFind 来解决这个问题。可以思考一下，如何实现？

这道题与 0200-number-of-islands.adoc 类似。

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:

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

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.

 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
/**
 * Runtime: 4 ms, faster than 22.25% of Java online submissions for Surrounded Regions.
 *
 * Memory Usage: 49.1 MB, less than 7.14% of Java online submissions for Surrounded Regions.
 *
 * Copy from: https://leetcode-cn.com/problems/surrounded-regions/solution/bfsdi-gui-dfsfei-di-gui-dfsbing-cha-ji-by-ac_pipe/[bfs+递归dfs+非递归dfs+并查集 - 被围绕的区域 - 力扣（LeetCode）]
 */
public void solve(char[][] board) {
    if (Objects.isNull(board) || board.length == 0) {
        return;
    }

    int yLength = board.length;
    int xLength = board[0].length;
    for (int y = 0; y < yLength; y++) {
        for (int x = 0; x < xLength; x++) {
            boolean isEdge = y == 0 || y == yLength - 1
                    || x == 0 || x == xLength - 1;
            if (isEdge && board[y][x] == 'O') {
                dfs(board, y, x);
            }
        }
    }

    for (int y = 0; y < yLength; y++) {
        for (int x = 0; x < xLength; x++) {
            if (board[y][x] == 'O') {
                board[y][x] = 'X';
            }
            if (board[y][x] == '#') {
                board[y][x] = 'O';
            }
        }
    }
}

private void dfs(char[][] board, int y, int x) {
    if (y < 0 || y >= board.length || x < 0 || x >= board[0].length
            || board[y][x] == 'X'
            || board[y][x] == '#') {
        return;
    }
    board[y][x] = '#';
    dfs(board, y - 1, x);
    dfs(board, y + 1, x);
    dfs(board, y, x - 1);
    dfs(board, y, x + 1);
}