Python程序：检查走出迷宫所需的指南针使用次数是否足够

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

因此，如果输入类似于grid =

n = 4, m = 11, k = 3；则输出将为True。

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

• 定义一个函数path_search()。这将接收curr_pos、grid、total_rows、total_cols、k、predecessor。

  • x:= curr_pos的x值

  • y:= curr_pos的y值

  • 如果grid[x, y]与"*"相同，则

    • 如果k与0相同，则

      • 返回True

    • 否则，

      • 返回False

    • 否则，

      • parent := predecessor[curr_pos]

      • succ_pos := 从succesor_positions(curr_pos, grid, total_rows, total_cols, parent)的返回值创建一个新列表

      • use_compass := 如果succ_pos的大小> 1，则为True

      • 对于succ_pos中的每个位置，执行：

        • predecessor[position] := curr_pos

        • 如果use_compass不为零，则

          • path_search(position, grid, total_rows, total_cols, k - 1, predecessor)

        • 否则，

          • path_search(position, grid, total_rows, total_cols, k, predecessor)

• 定义一个函数succesor_positions()。这将接收curr_pos、grid、total_rows、total_cols、parent。

  • x:= curr_pos的x值

  • y:= curr_pos的y值

  • succ_pos := 一个新列表

  • 如果y > 0，则

    • left := x, y - 1

    • 将left插入succ_pos的末尾

  • 如果y < total_cols - 1，则

    • right := x, y + 1

    • 将right插入succ_pos的末尾

  • 如果x > 0，则

    • up := x - 1, y

    • 将up插入succ_pos的末尾

  • 如果x < total_rows - 1，则

    • down := x + 1, y

    • 将down插入succ_pos的末尾

  • 如果对于succ_pos中的每个位置，grid[position[0], pos[1]]

  • 不与"X"相同且pos不与parent相同，则：

    • 返回满足条件的succ_pos中的元素

现在执行以下操作：

• curr_pos := 一个新的空对

• 对于每个索引i，grid中的每一行item，执行：

  • 对于每个索引j，行中的每个元素item，执行：

    • 如果元素与'M'相同，则

      • curr_pos := 一个包含i, j的新对

• predecessor := 一个新的映射，其中curr_pos最初为Null

• path_search(curr_pos, grid, n, m, k, predecessor)

源代码 (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

Arnab Chakraborty

更新于：2021年8月30日

79 次浏览

开启您的职业生涯

完成课程获得认证

开始学习