← 返回题目列表

Codeforces · 676/D

D. 忒修斯和迷宫

中文机器翻译题面 查看原题

忒修斯刚刚抵达克里特岛与牛头怪战斗。他发现了一个迷宫,其形状为 n × m 的矩形区域,由大小为 1 × 1 的块组成。

迷宫的每个方块都有一个按钮,可以将所有方块顺时针旋转 90 度。每个方块都围绕其中心旋转,并且不会改变其在迷宫中的位置。此外,每个街区都有一定数量的门(可能没有)。一分钟内,忒修斯可以按下按钮使所有方块顺时针旋转 90 度,也可以传递到相邻的方块。仅当 A 块有通往 B 块的门且 B 块有通往 A 块的门时,忒修斯才能从 A 块到某个邻近的 B 块。

忒修斯找到了迷宫的入口,现在位于块 (xT, yT)——xT 行和 yT 列的块中。忒修斯知道牛头怪藏在块 (xM, yM) 中,并且想知道到达那里所需的最少分钟数。

These修斯是英雄,不是程序员,所以他请求你帮助他。

输入

输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 1000) - 分别是迷宫中的行数和列数。

接下来的n行每行包含m个字符,描述迷宫的方块。可能的字符有:

- «+» 表示该街区有 4 扇门(每个相邻街区一扇门);
- «-» 表示该街区有 2 扇门 — 向左和向右邻居;
- «|»意味着这个街区有 2 个门——通向顶部和底部的邻居;
- «^» 表示该块有 1 扇门 — 通向最上面的邻居;
- «>» 表示该街区有 1 扇门 — 通向右侧邻居;
- «<» 表示该街区有 1 扇门 — 通往左侧邻居;
- «v» 表示该街区有 1 扇门 — 通往底部邻居;
- «L» 表示该街区有 3 扇门 — 通往除左边一扇之外的所有邻居;
- «R» 表示该街区有 3 扇门 — 通往除右边一扇之外的所有邻居;
- «U» 表示该街区有 3 扇门 — 通往除顶部一扇之外的所有邻居;
- «D» 表示该街区有 3 扇门 — 通往除底部一扇之外的所有邻居;
- «*» 表示该街区是一堵墙并且没有门。

左、右、上、下的定义是将迷宫表示为一个表格,其中行从上到下编号为 1 到 n,列从左到右编号为 1 到 m。

下一行包含两个整数 - 块的坐标 (xT, yT) (1 ≤ xT ≤ n, 1 ≤ yT ≤ m),这是Theseus 最初所在的位置。

最后一行包含两个整数 - 牛头怪隐藏的方块坐标 (xM, yM) (1 ≤ xM ≤ n, 1 ≤ yM ≤ m)。

保证忒修斯开始的方块和牛头怪躲藏的方块都至少有一扇门。忒修斯和牛头怪最初可能位于同一个街区。

输出

如果Theseus 无法到达 Minotaur,则在输出的唯一行中打印 -1。否则,打印到达牛头怪隐藏的区块所需的最少分钟数。

示例

输入 #1

2 2
+*
*U
1 1
2 2

输出 #1

-1

输入 #2

2 3
<><
><>
1 1
2 1

输出 #2

4

注意

假设Theseus 从时刻 0 的块 (xT, yT) 开始。