5501 - 迷路

通过次数

4

提交次数

11

时间限制 : 1 秒
内存限制 : 256 MB

小胖独自进入古城探险,结果迷路了,现在他手中有一张带有标记的地图,但这张地图很古老了,准确性不高,好在他现在处于一个非常明显的标志物附近,很容易就在地图上找到了自己的位置,天色越来越晚了,小胖只能按地图来试一试了,他仔细观察后确认地图是一个R行C列的矩阵,每个点上的数字代表经过此处的难度(难度值为1~9),难度值就是通过此处的时间,如果难度值为0就证明此处无法通过,在某个点可以向任意方向尝试(共8个方向),请你帮小胖看一看能否走出古城,如果能,最少需要多少时间。

输入

第一行由空格隔开的2个整数,分别是R和C(2<=R,C<=50)
之后的R行,每行是C个用空格隔开的数字C_i(0<=C_i<=9)
之后一行是4个由空格隔开的数值,前两个表示小胖现在位置的横纵坐标,后两个表示古城出口的横纵坐标(这两个点的值都不是0)

输出

如果不能走出古城输出-1
如果可以走出,输出所需最短时间
注意:起点和出口都不耗费时间,出口保证在矩阵的四周

样例

输入

6 5
1 2 6 0 1
3 2 0 9 7
5 6 8 2 5
0 1 2 0 3
8 1 5 0 7
2 6 4 3 2
2 2 5 5

输出

13

来源

自编