Leetcode 130. 被围绕的区域

发表于
| 字数统计: 890 | 阅读时长 ≈ 3

题目描述

给定一个二维的矩阵，包含 '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（深度优先搜索）解决。

找到所有被X围绕的区域不容易，但是其等价于找到所有没有没有被X围绕的区域（连接边界的区域），这样就可以从边界上的O开始进行深度优先搜索，

举个例子：

1
2
3
4
X X X X
X X O X
X O X X
X O X X

对于上面这张图的边界，只有第四行第二列的内容是O，我们对其进行DFS，即DFS(3,1)
首先将它本身改为#

1
2
3
4
X X X X
X X O X
X O X X
X # X X

之后对该位置的上下左右进行搜索，即分别尝试DFS(2,1)，DFS(4,1)，DFS(3,0)，DFS(3,2)，如果越界或者内容不是O则停止搜索。

因为此位置左右是X，下面超出数组下边界，只有上面是O，所以继续进行DFS(2,1)。

1
2
3
4
X X X X
X X O X
X # X X
X # X X

和之前一样，先将其本身改为#，之后上下左右进行DFS，而对于此坐标上下左右都不是O，所以搜索结束。

最后遍历全图，将所有的#改为O，所有的O改为X即可。

最终结果：

1
2
3
4
X X X X
X X X X
X O 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
50
51
52
53
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        # 如果是空数组，直接返回
        # Leetcode总搞这种边边角角的输入
        if not board: return
        # 计算数组长宽
        row = len(board)
        col = len(board[0])
        # 如果长度或者宽度中一个小于3的话也不用算了，直接返回
        if row < 3 or col < 3: return
        # DFS函数
        def dfs(i, j):
        # 如果i，j中有一个越界或者遇到了X则不继续扫描
            if i < 0 or j < 0 or i >= row or j >= col or board[i][j] != 'O':
                return
            # 否则把数组中的O变成#，意思是这个O和边缘是连通的
            board[i][j] = '#'
            # 之后从当前坐标开始上下左右进行递归搜索
            dfs(i - 1, j)
            dfs(i + 1, j)
            dfs(i, j - 1)
            dfs(i, j + 1)
        
        for i in range(row):
        # 搜索第一行和最后一行
            dfs(i, 0)
            dfs(i, col - 1)
        
        for i in range(col):
        # 搜索第一列和最后一列
            dfs(0, i)
            dfs(row - 1, i)

        # 全部搜索完毕后：
        # X X X X 
        # X X O X
        # X O X X
        # X O X X
        # 变为：    
        # X X X X
        # X X O X
        # X # X X
        # X # X X
        # 之后再将所有的#变成O，O变成X就可以了
        for i in range(0, row):
            for j in range(0, col):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                if board[i][j] == '#':
                    board[i][j] = 'O'

执行用时 :140 ms, 在所有Python3提交中击败了98.19%的用户
内存消耗 :14.6 MB, 在所有Python3提交中击败了74.24%的用户