1273:走迷宫

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

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

相关

厦门大学嘉庚学院第五届编程大赛

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

16级软件工程课程设计题

题单#8(BFS)


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