You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

已知一个 n * m 迷宫，迷宫的入口是左上角（1,1）的位置，而迷宫的出口在右下角（n,m）的位置。现在已知迷宫中每个位置都有两种状态，如果是 0 代表此位置是通行的，如果是 1 的话代表有障碍物而无法通行。现在请你编写程序，求出从入口走到出口的最少步数？（上下左右四个方向可以选择）

输入格式

输入 n+1 行：

第 1 行包含两个整数 n, m。

第 2~n+1 行，每行 m 个整数表示迷宫中每个位置的状态。

输出格式

输出 1 行，包含一个整数，表示走到出口所需的最少步数。

样例

5 5
0 1 0 0 1
0 0 0 0 1
1 1 0 0 1
0 0 0 1 0
0 0 0 0 0

8

提示

1≤ n, m ≤ 100。