#414. 迷宫最短路径

迷宫最短路径

题目描述

给定一个 n×mn\times m 的二维整数数组,用来表示一个迷宫。数组中只包含 00 或 11,其中 00 表示可以走的路,11 表示不可通过的墙壁。

最初,有一个人位于左上角 (1,1)(1,1) 处。每次可以向上、下、左、右任意一个方向移动一个位置(不能越界,也不能进入墙壁)。

求从左上角移动至右下角 (n,m)(n,m) 处,至少需要移动多少次。

数据保证 (1,1)(1,1) 和 (n,m)(n,m) 均为 00,且一定至少存在一条通路。

输入格式

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

接下来 nn 行,每行包含 mm 个整数(00 或 11),表示完整的二维数组迷宫。

输出格式

输出一个整数,表示从左上角移动至右下角的最少移动次数。

输入样例

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

输出样例

8

数据范围

1≤n,m≤1001\le n,m\le100。