2229: 邪狼走迷宫

Memory Limit：128 MB Time Limit：1 S
Judge Style：Text Compare Creator：
Submit：396 Solved：139

Description

邪狼为了躲避修罗王的追捕，不得不走进一个n行m列的迷宫。迷宫入口在第1行、第1列，出口在第n行、第m列。 虽然走进迷宫，暂时安全，但是，如果不能快速走出迷宫，最终还是会被修罗王捉住，因为修罗王知道他走进迷宫了，也会尽快堵住出入口。 那么，邪狼最终能不能逃过修罗王的追捕呢？先请你来算一算邪狼穿越迷宫至少需要多少时间吧！ 迷宫用0和1来描述，1代表有障碍物，0代表可以通过；邪狼在迷宫里每次移动只能从一个无障碍的单元移动到周围8个方向上任一无障碍单元，且需要消耗1个单位的时间。

Input

第一行：输入n和m两个正整数 接下来有n行，每行有m个0或1的数，每个数之间有一个空格。

Output

输出一个整数，如果可以通过迷宫，输出最少步数，否则输出0。

Sample Input Copy 

4 4
0 0 0 0
1 0 1 0
1 0 0 0
1 1 1 0

Sample Output Copy 

4

HINT

样例说明：进入迷宫的第一步，消耗1个单位时间，接着邪狼每次往右下角方向移动，一直到出口，共需要4个单位时间。 数据范围： 40%的数据，n、m<=50 60%的数据，n、m<=100 80%的数据，n、m<=300 90%的数据，n、m<=500 100%的数据，n、m<=1000 数据保证入口和出口的位置无障碍物

加入题单

算法标签：