走迷宫

题目描述

Y 同学迷失在一个大小为 $N \times M$ 的网格矩阵表示的迷宫中。

在矩阵中，数字 $0$ 表示空白处，可以通行；数字 $1$ 表示障碍物，不可通行。

初始时，Y 同学位于迷宫的左上角 $(1, 1)$ 处。每一秒钟，Y 同学可以沿着上、下、左、右四个方向之一移动到相邻的格子，前提是目标格子在迷宫内部，并且不是障碍物。

Y 同学的目标是走到迷宫的右下角 $(N, M)$ 处。请你计算他能否到达目的地。如果能够到达，求出所需的最短时间（秒数）；如果无法到达目的地，请输出 $-1$。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示迷宫矩阵的行数和列数。

接下来的 $N$ 行，每行包含 $M$ 个整数，每个整数为 $0$ 或 $1$，表示迷宫的地图。相邻的整数之间由一个空格隔开。

数据保证起点 $(1, 1)$ 和终点 $(N, M)$ 的位置均为 $0$。

输出格式

输出一行一个整数。若 Y 同学能够到达终点 $(N, M)$，则输出所需的最短时间；若无法到达，则输出 $-1$。

样例

样例输入 #1

5 5
0 1 0 0 0
0 0 0 1 0
1 1 0 1 0
0 0 1 0 0
1 0 0 1 0

样例输出 #1

10

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le N, M \le 1000$。