宇航员路径

题目描述

两名宇航员在探索一个未知行星，行星上有一些障碍物，这些障碍物用数字1表示，没有障碍物用数字0表示。行星被表示成一个N*M的矩阵。

探索过程中两名宇航员走散了。已知A宇航员的位置（x1, y1）和B宇航员的位置（x2, y2），请你帮助A宇航员寻找一条最短路径到达B宇航员的位置，并输出最短路径的长度（不包括起点）。

注意： 1. x1、x2表示矩阵的行号，y1、y2表示矩阵的列号； 2. 左上角的位置为(0,0)； 3. A、B宇航员的位置只能在数字0上； 4. 有障碍物的位置不能通过。例如：当N=4，M=5，x1=1，y1=0，x2=3，y2=3，A宇航员位置（1, 0），B宇航员位置（3, 3），矩阵表示如下：

A宇航员到B宇航员有2条路径：

第1条路径：(1, 0) -> (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (2, 2) -> (2, 3) -> (3, 3)，路径长度为7；

第2条路径：(1, 0) -> (2, 0) -> (2, 1) -> (2, 2) -> (2, 3) -> (3, 3)，路径长度为5；

其中最短路径长度为5。

输入描述

第一行包含两个正整数N（1<=N<=20）和M（1<=M<=20），分别表示矩阵的行数和列数，正整数之间一个空格隔开

接下来N行，每行包含M个数字（0或1），0表示行星上没有障碍物的位置，1表示行星上有障碍物的位置，整数之间一个空格隔开

最后一行包含四个整数x1（0<=x1<N），y1（0<=y1<M），x2（0<=2<N），y2（0<=y2<M），（x1, y1）表示A宇航员的位置，（x2, y2）表示B宇航员的位置，整数之间一个空格隔开

输出描述

输出一个整数，表示A宇航员到达B宇航员的最短路径长度。如果输入不符合要求，输出-2，如果无法到达，输出-1

样例输入

4 5

0 0 0 0 0

0 1 0 1 0

0 1 0 0 0

0 0 1 0 0

1 0 3 3

样例输出

7

代码详解

展开查看

n, m = [int(i) for i in input().split()]
ls = [[int(i) for i in input().split()] for i in range(n)]
x1, y1, x2, y2 = [int(i) for i in input().split()]

vis = [[0 for i in range(m)] for i in range(n)]
vis[x1][y1] = 1
queue = [[x1, y1, 0]]
d = [(1,0), (-1,0), (0,-1), (0,1)]

while len(queue) > 0:
    x, y = queue[0][0], queue[0][1]
    # print(queue)
    if x == x2 and y == y2:
        print(queue[-1][2])
        break
    for dx, dy in d:
        xx = x + dx
        yy = y + dy
        if 0 <= xx <n and 0 <= yy < m and vis[xx][yy] == 0 and ls[xx][yy] == 0:
            queue.append([xx, yy, queue[0][2] + 1])
            vis[xx][yy] = 1
            # print("append", queue)
    queue.pop(0)

运行结果

展开查看