UOJ Logo PP Online Judge

PPOJ

#113. 数据结构实验2-2: 地图探索

统计

描述

wym6912 是一个酷爱探险的探险家(是不可能的)。在现实生活中,他就是一个死肥宅!
死肥宅也是有梦想的。他有时候在想:如果我是一只小白鼠的话,我在一个一个 $n(n<=20)$行 $m(m<=20)$ 列迷宫,迷宫每个位置用整数 10 表示,0 表示墙, 1 表示通道里,我会怎么从起点 $(x_0, y_0)$ 走到 $(x_1, y_ 1)$ 啊?
他看到了在旁边看题的你,他就把这道题扔给你了。他说:“我的作业还没写完呢,写完作业你还没做完的话...hhh”

输入

输入数据第 $1$ 行为两个正整数 $n$ 和 $m$,分别表示迷宫的行数列数,第 $2$ 行为两个整数表示起点位置的行坐标和列坐标(行列坐标值从 $1$ 开始计算),第 $3$ 行为两个整数表示终点位置的行坐标和列坐标(行列坐标值从 $1$ 开始计算),后面紧跟 $n$ 行数据,每行数据由 $m$ 个整数构成,表示迷宫每个位置的状态。

输出

输出为最短路径步数,如果没有通路则输出-1

样例一

输入

8 8 
1 1 
5 7 
1 1 0 1 1 1 0 1
1 1 0 1 1 1 0 1
1 1 1 1 1 1 1 1
1 0 0 0 1 1 1 1
1 1 1 0 1 1 1 1
1 0 1 1 1 0 1 1
1 0 0 0 1 0 0 1
0 0 1 1 1 1 1 1

输出

10