给定一个 的网格。你从起点 出发,每一次可以向上、下、左、右移动一步(若不超出边界)。某些格子上存在障碍物,无法经过。求从 移动到终点 的最少步数;若无法到达,输出 。
输入描述:
在一行上输入两个整数 ,代表网格的行数与列数。在一行上输入四个整数 ,代表起点与终点的坐标。此后 行,第 行输入一个长度为 的字符串 ,其中若 ,表示第 行第 列为障碍物;若 ,表示该格子可通行。保证起点所在格子可通行。


输出描述:
输出一个整数,表示最少移动次数;若无法到达,输出 。
示例1

输入

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

输出

12
示例2

输入

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

输出

-1
示例3

输入

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

输出

-1
加载中...