刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！

简答题

编程实现：

两名宇航员在探泰一个未知行星，行星上有-一 些障碍物，这些障碍物用数字 1 表示，没有障碍物用数字 0 表示。

行星被表示成一个 N*M 的矩阵。

探素过程中两名宇航员走散了。已知 A 宇航员的位置 (×1,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≤x2<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 0 0 0 1
0 1 1 0 0
1 0 3 3

样例输岀：

5

使用微信搜索喵呜刷题，轻松应对考试！

答案：

```pythondef find_shortest_path(N, M, matrix, x1, y1, x2, y2):if x1 < 0 or x1 >= N or y1 < 0 or y1 >= M or x2 < 0 or x2 >= N or y2 < 0 or y2 >= M:return -2if matrix[x1][y1] == 1 or matrix[x2][y2] == 1:return -1queue = [(x1, y1, 0)]visited = set([(x1, y1)])directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]while queue:x, y, step = queue.pop(0)if x == x2 and y == y2:return stepfor dx, dy in directions:nx, ny = x + dx, y + dyif 0 <= nx < N and 0 <= ny < M and (nx, ny) not in visited and matrix[nx][ny] == 0:queue.append((nx, ny, step + 1))visited.add((nx, ny))return -1N, M = map(int, input().split())matrix = [list(map(int, input().split())) for _ in range(N)]x1, y1, x2, y2 = map(int, input().split())print(find_shortest_path(N, M, matrix, x1, y1, x2, y2))```

解析：

【喵呜刷题小喵解析】：
这个问题可以通过广度优先搜索（BFS）来解决。我们可以从 A 宇航员的位置开始，在行星矩阵中按照上下左右四个方向搜索，同时记录下已经走过的位置。每当我们搜索到一个新的位置，我们会检查是否达到了 B 宇航员的位置。如果达到，则返回路径长度；如果没有达到，我们会将新位置加入到搜索队列中，并更新已访问的位置集合。

如果搜索完所有可能的位置都没有找到 B 宇航员，则返回 -1。在搜索过程中，我们需要检查输入的位置是否在矩阵范围内，以及 A 和 B 宇航员的位置是否在有障碍物的位置上。如果输入不符合要求，则返回 -2。

在 Python 中，我们可以使用队列（queue）来存储待搜索的位置，使用集合（set）来存储已访问的位置，使用元组（tuple）来表示位置。在搜索过程中，我们按照广度优先的顺序搜索位置，即先搜索相邻的位置，再搜索更远的位置。

以上代码实现了广度优先搜索的算法，其中 `find_shortest_path` 函数用于找到最短路径长度。输入的位置通过 `input()` 函数读取，矩阵通过 `input().split()` 函数分割成行，每行再分割成列。最后，我们调用 `find_shortest_path` 函数并打印结果。
创作类型：
原创

本文链接：编程实现： 两名宇航员在探泰一个未知行星，行星上有-一 些障碍物，这些障碍物用数字 1 表示，没有障

版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！

分享考题
share