给定一个的网格,在网格中每次在不超过边界的情况下可以选择向上、向下、向左、向右移动一格。网格中的一些格子上放置有障碍物,放有障碍物的格子不能到达。求从到最少的移动次数。若不能到达,输出。
输入描述:
第一行输入两个整数 (),表示网格大小。第二行输入四个整数 (, ),表示起点和终点的坐标。接下来的行,每行输入一个长度为的字符串。其中,第行第个字符表示第行第列的格子上的障碍物情况,若字符为'*',则格子上有障碍物,若字符为'.',则格子上没有障碍物。保证起点不存在障碍物。


输出描述:
输出一行一个整数,表示从到最少的移动次数。
示例1

输入

5 5
1 1 5 5
.....
****.
.....
**.**
.....

输出

12
示例2

输入

5 5
1 1 4 5
.....
****.
.....
**.**
.....

输出

-1
示例3

输入

5 5
1 1 5 5
.....
****.
.....
*****
.....

输出

-1
加载中...