#214518. [JOISC 2016] 危险的滑冰 / Dangerous Skating

JOI 君喜欢在大自然中广阔的溜冰场上滑冰。

溜冰场是一个南北方向有 行、东西方向有 列的长方形网格。我们用 表示第 行、第 列的格子。每个格子要么是 JOI 君可以通行的，要么是布满冰块、无法通行的。此外，溜冰场外围的所有格子都布满冰块，JOI 君无法滑出溜冰场外。也就是说，格子 、（）以及格子 、（）上均有冰块。

JOI 君并不擅长滑冰。当他滑行时，只能朝东、西、南、北四个方向中的一个方向滑行，从当前所在的格子出发，一直滑到前方遇到冰块为止才停下。从滑行开始到停下为止算作一次移动。若相邻格子上有冰块，则不能朝该方向移动。

某日，JOI 君正在滑冰，突然发现：每当他完成一次移动，移动的起点会产生冰块。继续在这样状态下滑冰是非常危险的，因此 JOI 君希望尽快从溜冰场中脱身。

JOI 君当前位于格子 。为了安全脱身，他必须在出口格子 停下。请编写程序，计算从当前位置出发，至少需要多少次移动才能安全抵达出口格子。根据溜冰场的状态和 JOI 君的当前位置，有时他可能无论如何移动都无法抵达出口格子。请注意：即使 JOI 君在移动途中经过了出口格子，但若未在该格子停下，则不能视为成功脱身。

题目

给定溜冰场上冰块的分布、JOI 君的当前位置以及出口格子的位置，编写程序判断 JOI 君是否能从当前位置出发并最终停在出口格子上；若可以，则求出所需的最小移动次数。

从标准输入读取以下数据：

• 第 1 行包含两个整数 和 ，以空格分隔。这表示溜冰场南北方向有 行，东西方向有 列。
• 接下来的 行中，每行包含一个由 个字符组成的字符串。每个字符为 '.' 或 '#' 中的一个。第 行（）从左数第 个字符（）表示溜冰场格子 的初始状态：若该字符为 '.'，表示该格子可通行；若该字符为 '#'，表示该格子有冰块，不可通行。
• 接下来一行包含两个整数 和 ，以空格分隔。这表示 JOI 君的当前位置是格子 。
• 再接下来一行包含两个整数 和 ，以空格分隔。这表示溜冰场的出口位于格子 。

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

样例输入 1

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

样例输出 1

4

样例输入 2

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

样例输出 2

5

样例输入 3

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

样例输出 3

-1

样例输入 4

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

样例输出 4

0

样例解释

在输入样例 1 中，溜冰场的初始状态如下所示。标有白色方块的格子表示冰块，标有 'J' 的格子表示 JOI 君的当前位置，标有 'E' 的格子表示出口。

:::align{center} :::

首先，若 JOI 君向东移动，溜冰场的状态将变为如下：

:::align{center} :::

此后，JOI 君依次向西、向南、向北移动，即可在总共 4 次移动后于出口处停下。无法在 3 次或更少的移动内抵达出口，因此应输出 4。

在输入样例 4 中，JOI 君的当前位置即为出口格子，因此所需的移动次数为 0。

数据范围

所有输入数据均满足以下条件：

• 。
• 。
• 。
• 。
• 。
• 。
• 溜冰场外围的所有格子均布满冰块。即，格子 、（）以及格子 、（）上均有冰块。
• 格子 和格子 上没有冰块。

子任务

子任务 1 [13 分]

满足以下条件：

• 。
• 。
• 若 JOI 君能从当前位置出发并最终停在出口格子，则所需的移动次数不超过 10 次。

子任务 2 [65 分]

满足以下条件：

• 。
• 。

子任务 3 [22 分]

无额外限制。

翻译由 Qwen3-235B 完成