编程实现:
两名宇航员在探索一个未知行星,行星上有-一 些障碍物,这些障碍物用数字 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