Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem D: BugZhu走迷宫

Problem D: BugZhu走迷宫

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 41  Solved: 4
[Submit][Status][Web Board]

Description

BugZhu掉落了一个方形的迷宫中,手游还没点的BugZhu想要尽快离开迷宫。掉落的过程中BugZhu观察到迷宫是由正方形的方格构成的,整个迷宫长n,宽m。每个方格之间都存在墙进行隔开,不过大部分墙上都留有足够BugZhu通过的门。但也有一些门是不断打开关闭的。回忆了掉落过程中的发现,BugZhu绘制出这个迷宫的地图。在地图中,BugZhu用符号‘@’表示无法到达的格子,可能是门无法开启,可能是被石头阻碍了通道;用符号‘#’表示四周的门不断开关的方格;用符号‘.’表示能够正常通过的格子。不断开关的门呈现如下规律:

不断重复图中的情况,即第1s纵向的门打开,横行的门关闭;第2s纵向的门关闭,横向的门打开;第3s横向和纵向的门均打开;第4s横向和纵向的门均关闭;如此不断循环。开始移动时所有变换的门都呈现第1秒的情况。BugZhu每秒可以向前后左右前进一个方格或者原地等待,现在他想知道他走出迷宫需要的最小时间。

Input

不超过100组数据
每组数据第一行为n,m(1<=n,m<=100)。
接下来一行x1,y1,x2,y2(1<=x1,x2<=n;1<=y1,y2<=m)表示BugZhu掉落的位置和迷宫的出口。
接下来n行,每行m个字符表示BugZhu绘制的迷宫地图。

Output

每组数组输出一个数表示BugZhu需要的最少时间,如果BugZhu无法离开迷宫,输出-1。

Sample Input

3 3
1 1 3 3
...
.@.
.#.
3 3
1 1 3 3
...
.@#
.#.

Sample Output

4
5

HINT

[Submit][Status][Web Board]