题目描述

给定一个N行M列的迷宫，每次只能向上、下、左、右四个方向走一步，问从左上角(0,0)走至右下角(N-1,M-1)所需的最小步数。

输入格式

第一行为2个正整数N,M，用一个空格隔开
接下来N行，每行M个数，1表示可通过，0表示不可通过
（起始点和终止点也可能为0）

输出格式

一行，一个整数，表示最小步数，若不能到达，输出-1

输入样例

3 3
1 1 1
1 0 1
0 0 1

输出样例

4

数据范围

20%的数据，N或M为1
30%的数据，全部节点均为1
70%的数据，1<=N<=M<=5
100%的数据，1<=N<=M<=1000

限制

每个测试点时间1秒，内存128MiB