题目内容

给定一个 $n \times m$ 的二维网格，其中 $0$ 表示可通行，$1$ 表示墙壁。从左上角 $(0, 0)$ 出发，每次可以向上下左右四个方向移动一步（不能穿墙），求到达右下角 $(n-1, m-1)$ 的最短步数。如果无法到达，输出 $-1$。保证起点和终点都是 $0$。

输入描述

第一行输入两个整数 $n, m$（$2 \le n, m \le 500$）。

接下来 $n$ 行，每行 $m$ 个整数（$0$ 或 $1$，空格分隔），$0$ 表示可通行，$1$ 表示墙壁。

输出描述

输出一个整数，表示从左上角到右下角的最短步数。如果无法到达，输出 $-1$。

样例 $1$

输入

4 2
0 0
0 0
0 0
0 0

输出

4

样例 $2$

输入

2 3
0 0 0
0 0 0

输出

3