提示: 欢迎访问OurACM平台。
Problem 2186 小明的迷宫

Accept: 147    Submit: 481
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

小明误入迷宫,塞翁失马焉知非福,原来在迷宫中还藏着一些财宝,小明想获得所有的财宝并离开迷宫。因为小明还是学生,还有家庭作业要做,所以他想尽快获得所有财宝并离开迷宫。

Input

有多组测试数据。

每组数据第一行给出两个正整数n,m(0<n,m<=100)。代表迷宫的长和宽。

接着n行,每行m个整数。正数代表财宝(财宝的个数不超过10);负数代表墙,无法通过;0代表通道。

每次移动到相邻的格子,所花费的时间是1秒。小明只能按上、下、左、右四个方向移动。

小明的初始位置是(1,1)。迷宫的出口也在(1,1)。

Output

输出获得所有财宝并逃出迷宫所花费的最小时间,如果无法完成目标则输出-1。

Sample Input

3 3 0 0 0 0 100 0 0 0 0 2 2 1 1 1 1

Sample Output

4 4

Source

FOJ有奖月赛-2015年03月

Submit  Back  Status  Discuss