题目描述

题目译自 JOISC 2016 Day4 T1 「危険なスケート」

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 君想尽快离开这个冰场。

JOI 君目前在 $(r_1,c_1)$，为了从这个冰场离开，他需要停在出口 $(r_2,c_2)$ 上。请帮 JOI 计算至少需要移动多少次才能从目前位置离开冰场。由于冰场状况和你目前的位置的不同，JOI 君有可能无论如何移动都无法停在出口。注意 JOI 君必须要停在出口上，滑过出口是不可以的。

输入格式

第一行两个整数 $R,C$，表示这个冰场南北有 $R$ 格，东西有 $C$ 格；

接下来 $R$ 行，每行 $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

数据范围与提示

对于所有数据，满足 $3\le R,C\le 10^3,1\le r_1,r_2\le R,1\le c_1,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)$ 这两个单元格没有冰块。

详细子任务及附加条件如下表：