AT_joisc2016_j 危険なスケート

JOI 君的爱好是在大自然的广阔滑冰场上滑冰。 滑冰场呈长方形，由南北方向的 $R$ 个格子和东西方向的 $C$ 个格子组成。我们将北边第 $r$ 行、西边第 $c$ 列的格子称为格子 $( r , c )$ 。每个格子要么是 JOI 君可以通过的格子，要么是有冰块而无法通过的格子。此外，滑冰场的外周的格子上都有冰块，JOI君不会滑出场外。也就是说，格子 $( i , 1 )$、$( i , C ) (1 ≦ i ≦ R)$ 以及格子 $( 1 , j )$、$( R , j ) (1 ≦ j ≦ C)$ 上都有冰块。 JOI 君的滑冰技术并不好。JOI 君在滑冰场上移动时，会朝东、西、南、北其中一个方向滑出当前所在的格子，并在撞到冰块的前一个格子停下。滑出去并停下的过程算作一次移动。如果相邻的格子上有冰块，则无法朝该方向移动。 有一天，JOI 君在享受滑冰时，突然发现当他滑出格子时，那个格子上会长出冰块。除了滑出格子的地方，经过的格子上不会长出冰块。在这种情况下继续滑冰非常危险，因此 JOI 君想尽快逃离这个滑冰场。 JOI 君当前的位置是格子 $( r1 , c1 )$。要从这个滑冰场逃脱，必须在出口的格子 $( r2 , c2 )$ 停下。为了让 JOI 君安全地从滑冰场逃脱，请编写一个程序，计算从当前位置开始移动到出口的格子至少需要多少次移动。可能会出现无论如何移动都无法停在出口的格子的情况。请注意，仅仅经过而不是停在出口的格子并不能算作逃离滑冰场。 给定滑冰场上冰块的信息、JOI 君的当前位置和出口的格子的位置，请判断 JOI 君是否能够从当前位置开始移动并在出口的格子停下，如果可以，则求出所需的最小移动次数。

从标准输入读取以下数据。 第一行包含两个整数 $R$ 和 $C$，以空格分隔。这表示滑冰场的大小为南北 $R$ 个格子，东西 $C$ 个格子。 接下来的 $R$ 行中，每行有一包含 $C$ 个字符的字符串。每个字符是 `.` 或 `#` 之一。第 $r$ 行 $( 1 \leq r \leq R )$ 的第 $c$ 个字符 $( 1 \leq c \leq C )$ 表示滑冰场的格子 $( r , c )$ 的初始状态。当这个字符是 `.` 时，表示该格子可以通过；当这个字符是 `#` 时，表示该格子上有冰块，无法通过。 接下来的一行包含两个整数 $r1$ 和 $c1$，以空格分隔。这表示 JOI 君的当前位置是格子 $( r1 , c1 )$。 接下来的一行包含两个整数 $r2$ 和 $c2$，以空格分隔。这表示滑冰场的出口是格子 $( r2 , c2 )$。

在标准输出中，输出 JOI 君从当前位置开始移动并在出口的格子停下所需的最小移动次数的整数，输出一行。如果 JOI 君无论如何移动都无法在出口的格子停下，则输出 $-1$。 ### 限制 $3 \leq R \leq 1000$，$3 \leq C \leq 1000$，$1 \leq r1 , r2 \leq R$，$1 \leq c1 , c2 \leq C$。 滑冰场的外周的格子上都有冰块。也就是说，格子 $( i , 1 )$、$( i , C ) ( 1 \leq i \leq R )$ 以及格子 $( 1 , j )$、$( R , j ) ( 1 \leq j \leq C )$ 上都有冰块。 格子 $( r1 , c1 )$ 和格子 $( r2 , c2 )$ 上没有冰块。

#### 子任务 $1$（$13$ 分） $R \leq 10$，$C \leq 10$。 如果 JOI 君能够从当前位置开始移动并在出口的格子停下，则所需的移动次数在 $10$ 次以内。 #### 子任务 $2$（$65$ 分） $R \leq 200$，$C \leq 200$。 #### 子任务 $3$（$22$ 分） 没有额外的限制。 翻自[此处](https://www2.ioi-jp.org/camp/2016/2016-sp-tasks/2016-sp-d4.pdf)。