P14402 [JOISC 2016] 危险的滑冰 / Dangerous Skating

JOI 君喜欢在大自然中广阔的溜冰场上滑冰。 溜冰场是一个南北方向有 $R$ 行、东西方向有 $C$ 列的长方形网格。我们用 $(r, c)$ 表示第 $r$ 行、第 $c$ 列的格子。每个格子要么是 JOI 君可以通行的，要么是布满冰块、无法通行的。此外，溜冰场外围的所有格子都布满冰块，JOI 君无法滑出溜冰场外。也就是说，格子 $(i, 1)$、$(i, C)$（$1 \le i \le R$）以及格子 $(1, j)$、$(R, j)$（$1 \le j \le C$）上均有冰块。 JOI 君并不擅长滑冰。当他滑行时，只能朝东、西、南、北四个方向中的一个方向滑行，从当前所在的格子出发，一直滑到前方遇到冰块为止才停下。从滑行开始到停下为止算作一次移动。若相邻格子上有冰块，则不能朝该方向移动。 某日，JOI 君正在滑冰，突然发现：每当他完成一次移动，移动的起点会产生冰块。继续在这样状态下滑冰是非常危险的，因此 JOI 君希望尽快从溜冰场中脱身。 JOI 君当前位于格子 $(r_1, c_1)$。为了安全脱身，他必须在出口格子 $(r_2, c_2)$ 停下。请编写程序，计算从当前位置出发，至少需要多少次移动才能安全抵达出口格子。根据溜冰场的状态和 JOI 君的当前位置，有时他可能无论如何移动都无法抵达出口格子。请注意：即使 JOI 君在移动途中经过了出口格子，但若未在该格子停下，则不能视为成功脱身。 **题目** 给定溜冰场上冰块的分布、JOI 君的当前位置以及出口格子的位置，编写程序判断 JOI 君是否能从当前位置出发并最终停在出口格子上；若可以，则求出所需的最小移动次数。

从标准输入读取以下数据： - 第 1 行包含两个整数 $R$ 和 $C$，以空格分隔。这表示溜冰场南北方向有 $R$ 行，东西方向有 $C$ 列。 - 接下来的 $R$ 行中，每行包含一个由 $C$ 个字符组成的字符串。每个字符为 '.' 或 '#' 中的一个。第 $r$ 行（$1 \le r \le R$）从左数第 $c$ 个字符（$1 \le c \le C$）表示溜冰场格子 $(r, c)$ 的初始状态：若该字符为 '.'，表示该格子可通行；若该字符为 '#'，表示该格子有冰块，不可通行。 - 接下来一行包含两个整数 $r_1$ 和 $c_1$，以空格分隔。这表示 JOI 君的当前位置是格子 $(r_1, c_1)$。 - 再接下来一行包含两个整数 $r_2$ 和 $c_2$，以空格分隔。这表示溜冰场的出口位于格子 $(r_2, c_2)$。

在标准输出中，输出一行整数，表示 JOI 君从当前位置出发并最终停在出口格子所需的最小移动次数。如果无论怎样移动都无法在出口格子停下，则输出 -1。

### 样例解释 在输入样例 1 中，溜冰场的初始状态如下所示。标有白色方块的格子表示冰块，标有 'J' 的格子表示 JOI 君的当前位置，标有 'E' 的格子表示出口。 :::align{center}  ::: 首先，若 JOI 君向东移动，溜冰场的状态将变为如下： :::align{center}  ::: 此后，JOI 君依次向西、向南、向北移动，即可在总共 4 次移动后于出口处停下。无法在 3 次或更少的移动内抵达出口，因此应输出 4。 在输入样例 4 中，JOI 君的当前位置即为出口格子，因此所需的移动次数为 0。 ### 数据范围 所有输入数据均满足以下条件： - $3 \le R \le 1000$。 - $3 \le C \le 1000$。 - $1 \le r_1 \le R$。 - $1 \le c_1 \le C$。 - $1 \le r_2 \le R$。 - $1 \le c_2 \le C$。 - 溜冰场外围的所有格子均布满冰块。即，格子 $(i, 1)$、$(i, C)$（$1 \le i \le R$）以及格子 $(1, j)$、$(R, j)$（$1 \le j \le C$）上均有冰块。 - 格子 $(r_1, c_1)$ 和格子 $(r_2, c_2)$ 上没有冰块。 ### 子任务 **子任务 1 [13 分]** 满足以下条件： - $R \le 10$。 - $C \le 10$。 - 若 JOI 君能从当前位置出发并最终停在出口格子，则所需的移动次数不超过 10 次。 **子任务 2 [65 分]** 满足以下条件： - $R \le 200$。 - $C \le 200$。 **子任务 3 [22 分]** 无额外限制。 翻译由 Qwen3-235B 完成