普及/提高-⏱ 1000ms💾 256MB#P5009

题目描述

小老鼠在 $n \times m$ 的迷宫里找奶酪:0 表示空地,1 表示墙壁。它从左上角 $(1,1)$ 出发,每次可以上下左右走一格,不能穿墙。

输出到达右下角 $(n, m)$最少步数;无法到达输出 -1

输入格式

第一行,两个整数 $n, m$,用空格分隔。

接下来 $n$ 行,每行 $m$ 个整数(01),用空格分隔。

输出格式

一行,一个整数,表示最少步数;无法到达输出 -1

数据范围

$$1 \le n, m \le 500$$

样例输入 #1
3 3
0 0 1
1 0 1
1 0 0
样例输出 #1
4
样例输入 #2
3 3
0 1 1
1 1 1
1 1 0
样例输出 #2
-1