Python中逃离迷宫矩阵的最小移动次数

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

所以，如果输入是这样的

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

示例

让我们看看以下实现以获得更好的理解 -

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