题目内容

冷链库区的地坪划成 $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

输入

2 3
0 1 0
0 0 0

输出

4

说明

一条最短走法是 $(0,0)\to(1,0)\to(1,1)\to(1,2)$，共 4 格。中间上方那格是货架，不能从第一行横穿。

样例2

输入

2 2
0 1
1 0

输出

-1

说明

两条空地不相邻，无法到达。

样例3

输入

1 1
0

输出

1

说明

起点就是终点，只需站在这一格，长度为 1。