Python程序：找出到达目标的最短路径

假设我们有一个网格，网格中的单元格包含各种符号，例如'X'、'O'、'*'和'#'，这些符号具有不同的含义。

• '#' 是我们要到达的目标单元格。
• 'O' 是我们可以通过它到达目标单元格的自由单元格。
• '*' 是我们在单元格中的位置。
• 'X' 是一个被阻塞的单元格，我们无法通过它移动。

我们必须找出从我们在网格中的当前位置到达目标单元格所需的步数。如果目标不可达，我们返回-1。网格作为输入提供给程序。

因此，如果输入类似于

则输出将为2

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

• m := 网格的行数
• n := 网格的列数
• 对于 i 从 0 到 m，执行：
  • 对于 j 从 0 到 n，执行：
    • 如果 grid[i, j] 等于 "*"，则：
      • 退出循环
    • 否则：
      • 继续下一次迭代
    • 退出循环
• ans := 0
• queue := 一个新的列表，包含整数对 (i, j)
• grid[i, j] := "X"
• 当 queue 不为空时，执行：
  • ans := ans + 1
  • newq := 一个新的列表
  • 对于 queue 中的每个 i, j，执行：
    • 对于 (i-1, j) , (i, j-1) , (i, j+1) , (i+1, j) 中的每个 ii, jj，执行：
      • 如果 0 <= ii < m 且 0 <= jj < n 且 grid[ii, jj] 不等于 "X"，则：
        • 如果 grid[ii, jj] 等于 "#"，则：
          • 返回 ans
        • 将 ii, jj 插入 newq 的末尾
        • grid[ii, jj] := "X"
  • queue := newq
• 返回 -1

示例

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

def solve(grid):
   m, n = len(grid), len(grid[0])
   for i in range(m):
      for j in range(n):
         if grid[i][j] == "*": break
      else: continue
      break
   ans = 0
   queue = [(i, j)]
   grid[i][j] = "X"
   while queue:
      ans += 1
      newq = []
      for i, j in queue:
         for ii, jj in (i-1, j), (i, j-1), (i, j+1), (i+1, j):
            if 0 <= ii < m and 0 <= jj < n and grid[ii][jj] != "X":
               if grid[ii][jj] == "#": return ans
               newq.append((ii, jj))
               grid[ii][jj] = "X"
      queue = newq
   return -1

print(solve([['X', 'X', 'O', 'X'],['X', 'X', '*', 'X'],['X', '#',
'O', 'X'],['X', 'X', 'X', 'X']]))

输入

[['X', 'X', 'O', 'X'],
['X', 'X', '*', 'X'],
['X', '#', 'O', 'X'],
['X', 'X', 'X', 'X']]

输出

2

Arnab Chakraborty

更新于：2021年10月6日

358 次浏览

开启你的职业生涯

完成课程获得认证

开始学习