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

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

• ‘#’是我们要到达的目标单元格。
• ‘O’是我们可以通过它前往目标单元格的自由单元格。
• ‘*’是我们在单元格中的位置。
• ‘X’是一个被阻塞的单元格，我们不能通过它前往目标单元格。

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

因此，如果输入如下所示：

X	X	O	X
X	X	*	X
X	#	O	X
X	X	X	X

则输出将为2。

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

• m:=网格的行数
• n:=网格的列数
• 对于i从0到m循环，进行以下操作：
  • 对于j从0到n的循环，进行以下操作：
    • 如果grid[i，j]与“*”相同，则
    • 退出循环
    • 否则，
    • 进入下一个迭代
    • 跳出循环
• ans:=0
• 队列:=包含整数对(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
    • 如果grid[ii，jj]与“#”相同，则
      • 返回ans
    • 将ii，jj插入newq的末尾
    • grid[ii，jj]:=”X”
• 队列:=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