题目描述

高桥君想去鱼店买鳗鱼。

高桥君居住的城镇由 $H$ 行 $W$ 列的网格状区域构成，每个区域是道路或墙壁。
以下，将从上往下第 $i$ 行（$1 \leq i \leq H$）、从左往右第 $j$ 列（$1 \leq j \leq W$）的区域表示为区域 $(i, j)$。
各区域的信息由 $H$ 个长度为 $W$ 的字符串 $S_1, S_2, \ldots, S_H$ 给出。具体来说，当 $S_i$ 的第 $j$ 个字符（$1 \leq i \leq H$，$1 \leq j \leq W$）为 . 时，区域 $(i, j)$ 是道路；当为 # 时，区域 $(i, j)$ 是墙壁。

高桥君可以按任意顺序重复执行以下两种操作：

• 移动到上下左右相邻的、位于城镇内且为道路的区域。
• 选择一个上下左右方向，进行前踢。
  当高桥君进行前踢时，可以将当前区域在该方向上 前 1 格 和 前 2 格 的区域（如果它们是墙壁）变为道路。
  注意：即使前 1 格或前 2 格位于城镇外，仍然可以进行前踢操作，但城镇外的区域不会发生变化。

高桥君最初位于区域 $(A, B)$，想要到达位于区域 $(C, D)$ 的鱼店。
保证高桥君初始所在的区域及鱼店所在的区域是道路。
请计算高桥君到达鱼店所需的最小前踢次数。

输入格式

输入通过标准输入给出，格式如下：

$H$ $W$
$S_1$
$S_2$
$\vdots$
$S_H$
$A$ $B$ $C$ $D$

输出格式

输出高桥君到达鱼店所需的最小前踢次数。

输入输出样例 #1

输入 #1

10 10
..........
#########.
#.......#.
#..####.#.
##....#.#.
#####.#.#.
.##.#.#.#.
###.#.#.#.
###.#.#.#.
#.....#...
1 1 7 1

输出 #1

1

输入输出样例 #2

输入 #2

2 2
.#
#.
1 1 2 2

输出 #2

1

输入输出样例 #3

输入 #3

1 3
.#.
1 1 1 3

输出 #3

1

输入输出样例 #4

输入 #4

20 20
####################
##...##....###...###
#.....#.....#.....##
#..#..#..#..#..#..##
#..#..#....##..#####
#.....#.....#..#####
#.....#..#..#..#..##
#..#..#.....#.....##
#..#..#....###...###
####################
####################
##..#..##...###...##
##..#..#.....#.....#
##..#..#..#..#..#..#
##..#..#..#..#..#..#
##.....#..#..#..#..#
###....#..#..#..#..#
#####..#.....#.....#
#####..##...###...##
####################
3 3 18 18

输出 #4

3

说明/提示

约束条件

• $1 \leq H \leq 1000$
• $1 \leq W \leq 1000$
• $S_i$ 是仅由 . 和 # 组成的长度为 $W$ 的字符串
• $1 \leq A, C \leq H$
• $1 \leq B, D \leq W$
• $(A, B) \neq (C, D)$
• $H, W, A, B, C, D$ 均为整数
• 高桥君初始所在的区域及鱼店所在的区域保证是道路

样例解释 1

高桥君最初位于区域 $(1, 1)$。通过反复移动到道路区域，可以到达区域 $(7, 4)$。在区域 $(7, 4)$ 向左方向进行前踢后，区域 $(7, 3)$ 和 $(7, 2)$ 会从墙壁变为道路。之后，通过反复移动（包括新变为道路的区域）即可到达位于区域 $(7, 1)$ 的鱼店。此时前踢次数为 $1$ 次，且无法在不使用前踢的情况下到达鱼店，因此输出 $1$。

样例解释 2

高桥君最初位于区域 $(1, 1)$。向右方向进行前踢后，区域 $(1, 2)$ 会从墙壁变为道路（向右前 2 格超出城镇范围，因此无变化）。之后可以从区域 $(1, 1)$ 移动到区域 $(1, 2)$，再到达区域 $(2, 2)$ 的鱼店。此时前踢次数为 $1$ 次，且无法在不使用前踢的情况下到达鱼店，因此输出 $1$。

样例解释 3

前踢操作可能影响包含鱼店所在区域的区画，但鱼店所在区域原本就是道路，因此不会发生变化。特别是前踢操作不会破坏鱼店。

翻译由 DeepSeek R1 完成