1273：走迷宫
时间限制：2 S / 内存限制：65536 KB
AC：339 / Submit：870
| 问题描述 |
|---|
五毒教总坛有一个复杂的迷宫用于阻挡外人进入，但复杂的迷宫并不会阻碍草原教主通过。为了能够更快地穿越迷宫，除了走迷宫正常的上下左右四个方向一次移动一格外，草原教主随身带了一个火箭背包，可以让她能够跳过一格障碍（当然中间没有障碍也能跳），跳的方向可以是上下左右四个方向之一。例如在下图中，红色表示障碍，灰色表示通路，那么从A点可以跳到B点，也可以从A点跳到C点，但不能从C点跳到D点。
不过火箭背包的能量有限，只够跳一次。假设走一格和跳一次花费的时间都是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 |
| 样例输出 |
4 |
| 提示说明 |
4秒的走法有很多种，其中有一种是从左上角的0处向右跳、向右、向下、向下，到达终点。 |
| 相关 |
