1274:走迷宫-2

时间限制:2 S   /  内存限制:65536 KB
AC:286   /  Submit:433
问题描述

五毒教总坛有一个复杂的迷宫用于阻挡外人进入,但复杂的迷宫并不会阻碍草原教主通过。为了能够更快地穿越迷宫,除了走迷宫正常的上下左右四个方向一次移动一格外,草原教主随身带了一个火箭背包,可以让她能够跳过一格障碍(当然中间没有障碍也能跳),跳的方向可以是上下左右四个方向之一。例如在下图中,红色表示障碍,灰色表示通路,那么从A点可以跳到B点,也可以从A点跳到C点,但不能从C点跳到D点。

不过火箭背包的能量有限,最多只能跳3次,并且火箭背包的质量很好,可以跳完一次以后立即跳下一次。假设走一格和跳一次花费的时间都是1秒,那么从指定的某个起点到达某个终点,最快需要花费多少秒时间?

输入描述

只有一组案例。

两个正整数m和n(m<=100,n<=100),表示迷宫的高度和宽度。

然后是m行数据,每行数据有n个整数,以空格相隔。每个数字代表的含义是:-1表示该点是障碍物,1表示该点是通路,0表示该点是起点或者终点。这m*n个数字中只会有2个数字是0。

输出描述

一个整数,表示从起点到终点最快需要多少秒。如果从起点无法到达终点则输出-1。不要换行。

样例输入复制样例

4 4

0 -1 1 1

1 -1 1 1

1 -1 -1 0

1 1 1 1

样例输出

3

提示说明

从左上角的0处向右跳、向右、向下跳,到达终点。

相关

信息学院编程竞赛题2017/04/08(导出当练习)

16级软件工程课程设计题

题单#8(BFS)


Copyright 2016 - 2024 XUJC ACM Team
闽ICP备2020022076号-1