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]与“*”相同,则
- 退出循环
- 否则,
- 进入下一个迭代
- 跳出循环
- 对于j从0到n的循环,进行以下操作:
- 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