6053: 撞撞飞车
[Creator : ]
Description
小 Z 是一名忠实的游戏爱好者，最近他迷上了一款叫作《撞撞飞车》的赛车类游戏。
游戏规则非常简单，小 Z 需要控制一名赛车从起点开到终点。这个游戏有个自定义模式，可以自己设计地图，于是小 Z 设计了一个 $M*N$ 的矩形格点地图，小 Z 设置了游戏的起点和终点，并且在地图里放置了一些障碍物。
已知小 Z 从任意一个格点 $(x,\ y)$ 可以移动到 $(x,\ y-1),\ (x,\ y+1),\ (x-1,\ y),\ (x+1,y)$ 四个格点中的任意一处，当且仅当这个目标格点在地图内且没有障碍物。
由于小 Z 刚刚学习这个游戏，还不太会操作赛车漂移转弯，所以他希望自己到终点的过程中尽量少转几次弯。
已知出发时小 Z 可以任意调整自己的车头方向，他想知道自己到达终点最小的转弯次数是多少？如果小 Z 无法到达终点，输出 $-1$。
游戏规则非常简单，小 Z 需要控制一名赛车从起点开到终点。这个游戏有个自定义模式，可以自己设计地图，于是小 Z 设计了一个 $M*N$ 的矩形格点地图，小 Z 设置了游戏的起点和终点，并且在地图里放置了一些障碍物。
已知小 Z 从任意一个格点 $(x,\ y)$ 可以移动到 $(x,\ y-1),\ (x,\ y+1),\ (x-1,\ y),\ (x+1,y)$ 四个格点中的任意一处，当且仅当这个目标格点在地图内且没有障碍物。
由于小 Z 刚刚学习这个游戏，还不太会操作赛车漂移转弯，所以他希望自己到终点的过程中尽量少转几次弯。
已知出发时小 Z 可以任意调整自己的车头方向，他想知道自己到达终点最小的转弯次数是多少？如果小 Z 无法到达终点，输出 $-1$。
Input
第一行包含两个整数 $M,\ N$，表示格点图的大小为 $M*N$。
第 $2$ 至 $M+1$ 行，每行一个 $N$ 长的字符串，表示小 Z 创建的地图。第 $i$ 行第 $j$ 个字符表示格点 $(i-1,\ j)$ 的状态，其中 . 代表可通行，* 代表有障碍物。
第 $M+2$ 行包含四个整数 $x_1,\ y_1,\ x_2,\ y_2$，表示起点为 $(x_1,\ y_1)$，终点为 $(x_2,\ y_2)$。
Output
输出一个整数 $K$，表示小 Z 从起点到终点最少需要转弯多少次。如果小 Z 无法到达终点，输出 $-1$。
Constraints
对于 $20\%$ 数据，$M=2$
对于 $50\%$ 数据，$M,\ N\le 10$
对于 $100\%$ 数据，$M,\ N\le 100,\ 1\le x_1,\ x_2\le M,\ 1\le y_1,\ y_2\le N$
Sample 1 Input
5 5
...**
*.**.
.....
.....
*....
1 1 3 1
Sample 1 Output
2
$(1,\ 1)->(1,\ 2)->(2,\ 2)->(3,\ 2)->(3,\ 1)$
在 $(1,\ 2)$ 处右转，在 $(3,\ 2)$ 处右转，一共拐弯两次。
Sample 2 Input
5 5
...**
*.**.
.*...
.....
*....
1 1 3 1
Sample 2 Output
-1
无法到达。