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

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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程