编程题

编程实现:

两名宇航员在探索一个未知行星,行星上有-一 些障碍物,这些障碍物用数字 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
查看答案
赣ICP备20007335号-2