Python 中迷宫矩阵的最小逃脱步数

假设我们有一个二进制矩阵，其中 0 表示空单元格，1 表示墙壁。如果我们从左上角 (0, 0) 开始，我们需要找到到达右下角 (R-1, C-1) 所需的最少单元格数。这里 R 是行数，C 是列数。如果我们找不到任何答案，则返回 -1。

因此，如果输入如下所示：

那么输出将是 8，因为我们可以选择如下路径：

为了解决这个问题，我们将遵循以下步骤：

• R := 行数
• C := 列数
• q := 一个空的列表，如果 matrix[0, 0] 为 0，则最初插入 (0, 0, 1)
• matrix[0, 0] := 1
• 对于 q 中的每个三元组 (r, c, d)，执行以下操作：
  • 如果 (r, c) 与 (R - 1, C - 1) 相同，则
    • 返回 d
  • 对于 [(r + 1, c) ,(r - 1, c) ,(r, c + 1) ,(r, c - 1) ] 中的每个 x, y，执行以下操作：
    • 如果 0 <= x < R 且 0 <= y < C 并且 matrix[x, y] 等于 0，则
      • matrix[x, y] := 1
      • 在 q 的末尾插入三元组 (x, y, d + 1)
• 返回 -1

示例

让我们看看以下实现，以便更好地理解：

def solve(matrix):
   R, C = len(matrix), len(matrix[0])
   q = [(0, 0, 1)] if not matrix[0][0] else []
   matrix[0][0] = 1
   for r, c, d in q:
      if (r, c) == (R - 1, C - 1):
         return d
      for x, y in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]:
         if 0 <= x < R and 0 <= y < C and matrix[x][y] == 0:
            matrix[x][y] = 1
            q.append((x, y, d + 1))
   return -1

matrix = [
   [0, 0, 0, 1, 0],
   [0, 0, 1, 1, 0],
   [0, 0, 0, 1, 1],
   [1, 1, 0, 0, 0]
]
print(solve(matrix))

输入

[
[0, 0, 0, 1, 0],
[0, 0, 1, 1, 0],
[0, 0, 0, 1, 1],
[1, 1, 0, 0, 0]
]

输出

8

Arnab Chakraborty

更新于: 2021-10-18

929 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习