题库 蓝桥杯青少组题库 题目列表 两名宇航员在探索一个未知行星,行星上有一些障碍物,...
问答题

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

题目信息
创意编程组 第十四届 STEMA 其他
-
正确率
0
评论
251
点击