在 Python 中检查指南针使用次数是否足以走出迷宫的程序

假设我们正在玩一个游戏，我们被困在迷宫中。我们必须找到走出迷宫的路。迷宫可以表示为 xm 矩阵，其中 n 是行数，m 是列数。矩阵的每个单元格/元素包含任何符号“O”、“D”、“S”或“-”。'O' 表示路径被阻塞，'D' 是迷宫的出路，'S' 是我们的起始位置，'-' 表示我们可以通过路径。我们可以在任何带有“-”标记的单元格中自由移动。现在，我们还有一个指南针，我们可以使用它找到迷宫的出口路径（“D”单元格）。当我们必须找到方向时，我们必须使用指南针。但是，我们最多可以使用指南针 k 次。将迷宫作为矩阵以及我们可以使用指南针的次数；我们必须弄清楚我们是否可以在使用指南针多次的情况下走出迷宫。如果可能，我们返回 True，否则我们返回 False。

所以，如果输入像 grid =

n = 4，m = 11，k = 3；那么输出将为True。

源代码 (Python)

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

def path_search(curr_pos, grid, total_rows, total_cols, k, predecessor):
   x, y = curr_pos
   if grid[x][y] == "D":
      if k == 0:
         print('True')
      else:
         print('False')
   else:
      parent = predecessor[curr_pos]
      succ_pos = list(succesor_positions(curr_pos, grid, total_rows, total_cols, parent))
      use_compass = len(succ_pos) > 1
      for position in succ_pos:
         predecessor[position] = curr_pos
         if use_compass:
            path_search(position, grid, total_rows, total_cols, k - 1, predecessor)
         else:
            path_search(position, grid, total_rows, total_cols, k, predecessor)

def succesor_positions(curr_pos, grid, total_rows, total_cols, pred):
   x, y = curr_pos
   succ_pos = []
   if y > 0:
      left = (x, y - 1)
      succ_pos.append(left)
   if y < total_cols - 1:
      right = (x, y + 1)
      succ_pos.append(right)
   if x > 0:
      up = (x - 1, y)
      succ_pos.append(up)
   if x < total_rows - 1:
      down = (x + 1, y)
      succ_pos.append(down)
   return filter(lambda pos: grid[pos[0]][pos[1]] != "O" and pos != pred, succ_pos)

def solve(grid, n, m, k):
   curr_pos = ()
   for i, row in enumerate(grid):
      for j, element in enumerate(row):
         if element == 'S':
            curr_pos = (i, j)
   path_search(curr_pos, grid, n, m, k, predecessor = {curr_pos: None})

grid = [['-', 'O', '-', 'O', '-', '-', '-', '-', '-', '-', 'O'],
['-', 'O', 'D', '-', 'O', '-', 'O', 'O', 'O', '-', 'O'],
['-', 'O', 'O', '-', 'O', '-', 'O', 'S', '-', '-', '-'],
['-', '-', '-', '-', '-', '-', 'O', 'O', 'O', 'O', '-']]

solve(grid, 4, 11, 3)

输入

grid = [['-', 'O', '-', 'O', '-', '-', '-', '-', '-', '-', 'O'],
['-', 'O', 'D', '-', 'O', '-', 'O', 'O', 'O', '-', 'O'],
['-', 'O', 'O', '-', 'O', '-', 'O', 'S', '-', '-', '-'],
['-', '-', '-', '-', '-', '-', 'O', 'O', 'O', 'O', '-']] , 4, 11, 3

输出结果

True