移动迷宫

题目描述

探险者被困在移动迷宫中。这个迷宫可以用一个 $n\times n$ 的方阵描述，每个格子上可能是：

• 空地，用 . 表示；
• 固定的墙壁，用 # 表示；
• 会移动的墙壁，用 U、D、L、R 表示，分别代表会向上、下、左、右四个方向移动的墙壁。

每天白天，探险者只能移动到上、下、左、右四个相邻格子的某一个，或者在原地停留。但是，不可以走进有墙壁的格子，也不可以走到方阵以外。

到了晚上，探险者会在原地休息，此时，所有会移动的墙壁将向其字母所代表的方向移动一格——如果有墙壁移动到探险者休息的位置，那么探险者将会窒息而亡，逃脱失败。如果墙壁移动前的位置上没有墙壁抵达且没有固定的墙壁，则该位置变为空地。到了白天，墙壁将停止移动，此时探险者再次启程。

此外，墙壁还有以下特性：

• 如果因为移动，两个墙壁到了同一个位置上，那么认为这个位置上有墙壁，并且下一晚上这两个墙壁仍然按照预定方式移动（如果是固定的墙壁则仍停在原地）。也就是说，墙壁重合不会对墙壁造成什么影响。
• 如果因为移动，墙壁移出了边界，那么它会瞬移到方阵的另一侧对应位置。也就是说，你可以认为方阵的上边界和下边界是相邻的，左边界和有边界是相邻的。例如，如果墙壁从 $(1,i)$ 这个位置向上移动一格，它将移动到 $(n,i)$；如果墙壁从 $(j,n)$ 这个位置向右移动一格，它将移动到 $(j,1)$。

现在，给出探险者的初始位置 $(sx,sy)$，以及出口所在位置 $(ex,ey)$，请你求出探险者至少在第几天才能到达出口（天数从 $1$ 开始计算，如果在第 $s$ 天的白天探险者从某个格子移动到出口所在格子，那么认为是在第 $s$ 天抵达出口的）。注：探险者一到达出口就会离开迷宫，也就是说不用再考虑当晚墙壁移动的影响。

当然，探险者也可能无法抵达出口，此时请输出 -1。

输入格式

第一行五个正整数 $n,sx,sy,ex,ey$，意义如题目描述。

接下来 $n$ 行，第 $i$ 行是一个长度为 $n$ 的字符串 $S_i$，我们用 $S_{i,j}$ 描述坐标 $(i,j)$ 格子上的情况。

输出格式

如果探险者可以抵达出口，则输出一个正整数，表示最小天数；否则输出 -1。

样例输入

5 1 1 2 5
..R##
UL#..
R...#
#....
DRRDR

样例输出

7

第一天往右走，第二天往下走，第三题往下走，第四天往右走，第五天往右走，第六天往上走，第七天往右走，抵达出口，因此共需 $7$ 天。

数据范围

本题共包含 $25$ 个测试点。对于全部测试数据，$2\le n\le 400,1\le sx,sy,ex,ey\le n$，保证初始位置和出口位置不同，保证初始位置上没有墙壁。