LeetCode130-被围绕的区域

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/surrounded-regions/

中文链接：https://leetcode-cn.com/problems/surrounded-regions/

题目详述

给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。

找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

示例:

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 X X X
X X X X
X O X X

解释:

被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

题目详解

DFS。把不与边界上的 'O' 相连的 'O' 变为 'X'。如果某一位置是 'O'，那么判断它与边界上的 'O' 是否相连，然后决定是否更改。但是这样比较麻烦，可以反过来思考，从边界上的 'O' 出发，找到这一整个连通区域，对这一区域的 'O' 做标记。处理完之后，做过标记的 'O' 不用更改，没做过标记的 'O' 改为 'X'。

  • 从四个边界上的 'O' 开始进行深搜。
  • 把边界区域内的所有 'O' 修改为 '1'（做标记，也可改为其他不冲突的字符）。
  • 最后把 'O' 改为 'X'， '1' 改为 '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
public class LeetCode_00130 {

    public void solve(char[][] board) {
        // 为空检查
        if (board == null || board.length == 0) {
            return;
        }
        int m = board.length;
        int n = board[0].length;
        // 把四个边界上的 'O' 的连通区域全部变为 '1'
        for (int i = 0; i < m; ++i) {
            dfs(board, i, 0);
            dfs(board, i, n - 1);
        }
        for (int i = 0; i < n; ++i) {
            dfs(board, 0, i);
            dfs(board, m - 1, i);
        }
        // 最后为 'O' 说明不与边界区域 'O' 连通，为 '1' 说明为边界 '0' 连通区域，恢复原状即可
        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] == '1') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    private void dfs(char[][] board, int i, int j) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != 'O') {
            return;
        }
        board[i][j] = '1';
        dfs(board, i - 1, j);
        dfs(board, i + 1, j);
        dfs(board, i, j - 1);
        dfs(board, i, j + 1);
    }
}