第33480题 程序题
求解网格障碍物环境下A宇航员到B宇航员的最短路径长度

两名宇航员在探索一个未知行星,行星上有一些障碍物,这些障碍物用数字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的最短路线用箭头表示,最短路线长度为7。

【输入描述】 第一行输入两个正整数N,M,正整数之间以空格隔开 接下来的N行,每行输入M个数,数字1表示障碍物,数字0表示没有障碍物,数字之间以空格隔开,第N+2行输入四个整数,分别表示x1,y1,x2,y2,整数之间以空格隔开

【输出描述】 输出一个数,表示A宇航员到达B宇航员位置的最短路径的长度(不包括起点)

【样例输入】

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
编辑模式
程序运行统计
暂无判题统计