走迷宫

题目描述

给定一个 $N\times M$ 的网格迷宫 $G$。$G$ 的每个格子要么是道路，要么是障碍物（道路用 $1$ 表示，障碍物用 $0$ 表示）。

已知迷宫的入口位置为 $(x_1,y_1)$，出口位置为 $(x_2 , y_2)$。问从入口走到出口，最少要走多少个格子。

输入描述

输入第 $1$ 行包含两个正整数 $N,M$，分别表示迷宫的大小。

接下来输入一个 $N\times M$ 的矩阵。若 $G_{i,j}=1$ 表示其为道路，否则表示其为障碍物。

最后一行输入四个整数 $x_1,y_1,x_2,y_2$，表示入口的位置和出口的位置。

$1\leq N,M\leq10^2$，$0\leq G_{i,j}\leq 1$，$1\leq x_1,x_2\leq N$，$1\leq y_1,y_2\leq M$。

输出描述

输出仅一行，包含一个整数表示答案。

若无法从入口到出口，则输出 $-1$。

输入输出样例

示例 1

>输入

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

>输出

8