传送门

题目描述

有一个纵 $H$ 格、横 $W$ 格、共 $H\times W$ 格的迷宫。

从上数第 $i$ 行、从左数第 $j$ 列的格子 $(i,j)$,当 $S_{ij}$ 为 # 时是墙壁,为 . 时是道路。

魔法师在格子 $(C_h,C_w)$。魔法师可以通过以下 $2$ 种方式移动:

• 移动 A:步行移动到与当前格子上下左右相邻的道路格子。
• 移动 B:用传送魔法移动到以当前格子为中心的 $5\times 5$ 范围内的道路格子。

无论哪种移动,都不能移动到迷宫外。

要移动到格子 $(D_h,D_w)$,最少需要使用多少次传送魔法?

输入格式

输入按以下格式从标准输入给出:

$H$ $W$
$C_h$ $C_w$
$D_h$ $D_w$
$S_{11}\ldots S_{1W}$
$\vdots$
$S_{H1}\ldots S_{HW}$

输出格式

输出使用传送魔法的最小次数。如果无法到达 $(D_h,D_w)$,则输出 -1。

样例

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

1

例如,步行移动到 $(2,2)$,再从 $(2,2)$ 用传送魔法移动到 $(4,4)$,可以把传送魔法的使用次数控制在 $1$ 次。

不能步行斜向移动。

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

-1

无法从当前位置移动。

4 4
2 2
3 3
....
....
....
....

0

不需要使用传送魔法。

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

2

数据范围

• $1 \leq H,W \leq 10^3$
• $1 \leq C_h,D_h \leq H$
• $1 \leq C_w,D_w \leq W$
• $S_{ij}$ 是 # 或 .
• $S_{C_h C_w}$ 和 $S_{D_h D_w}$ 是 .
• $(C_h,C_w) \neq (D_h,D_w)$