AT_abc400_d [ABC400D] Takahashi the Wall Breaker

[problemUrl]: https://atcoder.jp/contests/abc400/tasks/abc400_d 高桥君想去鱼店买鳗鱼。 高桥君居住的城镇由 $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 \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 完成