1274：走迷宫-2

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