题目描述

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。

5 5
#####
#...#
#...#
#...#
#####
2 2
3 3

4

8 6
######
#..#.#
##...#
#....#
#.#..#
#....#
##...#
######
4 3
6 4

5

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

-1

3 3
###
#.#
###
2 2
2 2

0

提示

样例解释

在输入样例 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 完成