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