题目描述

冷链库区的地坪被划分成 $h$ 行 $w$ 列的格子。格子取值 0 表示空地，可以踏入；取值 1 表示货架底座，禁止进入。值班员要从西北角格子 $(0,0)$ 走到东南角格子 $(h-1,w-1)$。每一步只能迈向上、下、左、右四个相邻格子中的空地，不允许斜向移动，也不得踏出库区。

路径长度定义为途经格子的个数，起点计入。请输出最短路径的长度；若无法抵达东南角，输出 -1。

约束：

• $1\le h,w\le 500$
• 每个格子的值是 0 或 1

输入描述

第一行两个整数 $h$、$w$（$1\le h,w\le 500$），表示行数和列数。

随后 $h$ 行，每行 $w$ 个整数，表示各地砖：0 为空地，1 为货架。

输出描述

输出一个整数：最短路径上的格子数；无法到达则输出 -1。

样例1

输入

3 4
0 0 1 0
1 0 0 0
0 0 1 0

输出

6

说明

一条最短走法是 $(0,0)\to(0,1)\to(1,1)\to(1,2)\to(1,3)\to(2,3)$，共 6 格。第一行第 3 格与第三行第 3 格是货架，不能沿这两行横穿到终点。曼哈顿距离对应的格子数也是 6，因此不存在更短路径。

样例2

输入

3 3
0 1 0
0 1 0
1 0 0

输出

-1

说明

从 $(0,0)$ 只能进入 $(1,0)$，而 $(1,0)$ 的四周不是货架就是已访问格子，无法再通向东南角。

样例3

输入

2 1
0
0

输出

2

说明

只有一列两格空地，走法是 $(0,0)\to(1,0)$，长度为 2。