题目描述

给定一个 n×m 的网格，其中 0 表示可走，1 表示障碍。 从 (1,1) 走到 (n,m)，每次可以上下左右移动，求最短路径长度。

若无法到达，输出 -1。

输入格式

n m

grid(网格)

输出格式

最短路径长度

样例

3 3
0 0 0
1 1 0
0 0 0

4

2 2
0 1
1 0

-1

Limitation

1s, 1024KiB for each test case.