You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

走迷宫

题目描述

你陷入了一个 $n \times m$ 的方形迷宫, 你只可以向上, 向下, 向左或向右移动, 其中 # 是墙, 不能移动到墙上, . 是路, 你可以在路上移动.

另外, 你还可以花费 $1$ 个金币进行跳跃, 比如你当前处于 $x, y$ 位置, 你可以跳跃到以 $x, y$ 为中心的 $5 \times 5$ 的任意非墙位置.

问你在迷宫中行走, 从 $x1, y1$ 到达 $x2, y2$ 位置, 最少需要花费多少枚金币?

数据格式

输入格式

第一行两个整数 $n, m$, 表示迷宫的行和列,

第二行是两个整数 $x1, y1$ 表示起点

第三行是两个整数 $x2, y2$ 表示终点.

接下来一个 $n \times m$ 的符号矩阵, 表示矩形迷宫, 只包含 . 或 #.

输出格式

输出一个整数, 表示最少花费多少枚金币即可到达终点, 如果永远无法到达终点, 请输出 -1

样例

3 4
1 1
3 4
.#..
..#.
..#.

1

4 5
1 1
4 5
.....
.....
.....
.....

0

4 5
1 1
4 5
.####
#####
#####
####.

-1

数据范围

$1 <= n, m <= 1000$

注意

需要读写文件, 读入文件名为 maze.in, 输出文件名为 maze.out