题目描述

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

溜冰场是一个南北方向有 $R$ 行、东西方向有 $C$ 列的长方形网格。我们用 $(r, c)$ 表示第 $r$ 行、第 $c$ 列的格子。每个格子要么是 lbw 可以通行的，要么是布满冰块、无法通行的。此外，溜冰场外围的所有格子都布满冰块，lbw 无法滑出溜冰场外。也就是说，格子 $(i, 1)$、$(i, C)$（$1 \le i \le R$）以及格子 $(1, j)$、$(R, j)$（$1 \le j \le C$）上均有冰块。

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

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

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

题目

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

输入格式

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

• 第 1 行包含两个整数 $R$ 和 $C$，以空格分隔。这表示溜冰场南北方向有 $R$ 行，东西方向有 $C$ 列。

• 接下来的 $R$ 行中，每行包含一个由 $C$ 个字符组成的字符串。每个字符为 '.' 或 '#' 中的一个。第 $r$ 行从左数第 $c$ 个字符表示溜冰场格子 $(r, c)$ 的初始状态：若该字符为 '.'，表示该格子可通行；若该字符为 '#'，表示该格子有冰块，不可通行。

• 接下来一行包含两个整数 $r_1$ 和 $c_1$，以空格分隔。这表示 lbw 的当前位置是格子 $(r_1, c_1)$。

• 再接下来一行包含两个整数 $r_2$ 和 $c_2$，以空格分隔。这表示溜冰场的出口位于格子 $(r_2, c_2)$。

输出格式

在标准输出中，输出一行整数，表示 lbw 从当前位置出发并最终停在出口格子所需的最小移动次数。如果无论怎样移动都无法在出口格子停下，则输出 -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' 的格子表示 lbw 的当前位置，标有 'E' 的格子表示出口。

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

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

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

子任务

子任务 1 [13 分]

满足以下条件：

• $R \le 10$。

• $C \le 10$。

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

子任务 2 [65 分]

满足以下条件：

• $R \le 200$。

• $C \le 200$。

子任务 3 [22 分]

无额外限制。

数据范围

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

• $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 \le r \le R$）

（$1 \le c \le C$）