用 Python 编写程序找出到达目标的最短路径

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

• '#' 是我们想要到达的目标单元格。
• 'O' 是一个空闲单元格，我们可以通过它到达目标单元格。
• '*' 是我们在单元格中的位置。
• 'X' 是一个被阻挡的单元格，我们无法通过它。

我们必须找出从网格中的当前位置到达目标单元格所需的移动次数。如果目标无法实现，则返回 -1。网格作为程序的输入。

因此，如果输入如下

则输出将为 2

要解决此问题，我们将遵循以下步骤 −

• m := row count of grid
• n := grid 的列数
• 对于 i 在 0 到 m 范围内，执行
  • 对于 j 在 0 到 n 范围内，执行
    • 如果 grid[i, j] 与 "*" 相同，则
      • 退出循环
    • 否则，
      • 进行下一次迭代
    • 退出循环
• ans := 0
• queue := 一个包含整数对 (i, j) 的新列表
• grid[i, j] := "X"
• 当队列不为空时，执行
  • ans := ans + 1
  • newq := 一个新列表
  • 对于队列中的每个 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
        • 在 newq 末尾插入 ii, jj
        • 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

相关文章

• Python 中通过 K 扩展列表
• Python - 使用交替的 0 和 1 初始化列表
• Python 中元组列表到字典的转换
• Python - 从两个列表中配对，使得成对的元素不相同
• 使用 Python 和 SQLite 的 SQL
• 使用 pytrie 模块在 Python 中进行前缀匹配
• 创建和访问 Python 包
• 如何使用正则表达式和数据类型选择多个 DataFrame 列
• 如何在 Pandas 中查找和过滤重复行?
• 用 Python 编写程序以正确的顺序查找机场?

有用资源

• python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/