A25690. 编程实现：两名宇航员在探索一个未知行星，行星上有-一 些障碍物，这些障碍物用数字 1 表示，没有障碍物用数字 0 表示。行星被表示成一个 N*M 的矩阵。探素过程中两名宇航员走散了。已知 A 宇航员的位置 (×1,y1)和 B 宇航员的位置(x2,y2)，请你帮助 A 宇航员寻找一条最短路径到达 B 宇航员的位置，并输出最短路径的长度（不包括起点）。注意：1.x1、x2 表示矩阵的行号，y1、y…
题目描述
编程实现：
两名宇航员在探索一个未知行星，行星上有-一 些障碍物，这些障碍物用数字 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参考答案
#参考答案1
from collections import deque
# 定义四个方向
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
# 读入数据
n, m = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]
x1, y1, x2, y2 = map(int, input().split())
# 定义队列和标记数组
q = deque()
visited = [[False] * m for _ in range(n)]
# 将起点加入队列
q.append((x1, y1))
visited[x1][y1] = True
# 定义步数变量
step = 0
# BFS搜索
while q:
size = len(q)
for _ in range(size):
x, y = q.popleft()
if x == x2 and y == y2:
print(step)
exit()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < n and 0 <= ny < m and matrix[nx][ny] == 0 and not visited[nx][ny]:
q.append((nx, ny))
visited[nx][ny] = True
step += 1
# 没有搜索到终点，返回-1
print(-1)
#参考答案2
s=input().split(' ')
row=int(s[0])
col=int(s[1])
matrix=[]
flags=[]
for i in range(row):
cols=input().split(' ')
matrix.append(cols)
flags.append([0]*col)
s=input().split(' ')
xa,ya,xb,yb=int(s[0]),int(s[1]),int(s[2]),int(s[3])
input_ok=1
if matrix[xa][ya]=='1' or matrix[xb][yb]=='1':
input_ok=0
min_steps=9999999999999
goal=False
def walk(x,y,steps):
global min_steps,goal,xa,ya,xb,yb,flags,matrix
if steps>=min_steps: # 减少无效搜索
return
if x==xb and y==yb:
if steps<min_steps:
min_steps=steps
goal=True
return
flags[x][y]=1
if y+1<col and matrix[x][y+1]=='0' and flags[x][y+1]==0:
walk(x,y+1,steps+1)
if y-1>=0 and matrix[x][y-1]=='0' and flags[x][y-1]==0:
walk(x,y-1,steps+1)
if x+1<row and matrix[x+1][y]=='0' and flags[x+1][y]==0:
walk(x+1,y,steps+1)
if x-1>=0 and matrix[x-1][y]=='0' and flags[x-1][y]==0:
walk(x-1,y,steps+1)
flags[x][y]=0
if input_ok==0:
print(-2)
else:
walk(xa,ya,0)
if goal:
print(min_steps)
else:
print(-1)答案解析
评分标准：
5 分：能正确输出第一组数据；
5 分：能正确输出第二组数据；
5 分：能正确输出第三组数据；
5 分：能正确输出第四组数据;
5 分：能正确输出第五组数据;
5 分：能正确输出第六组数据。