CF676D Theseus and labyrinth

Theseus 刚刚到达克里特岛，准备与米诺陶战斗。他发现了一个迷宫，这个迷宫的形状是一个 $n\times m$ 的矩形区域，由 $1\times 1$ 的方块组成。 迷宫中的每个方块都有一个按钮，可以将所有方块顺时针旋转 $90$ 度。每个方块会围绕自身中心旋转，且在迷宫中的位置不会改变。同时，每个方块上还有若干扇门（也可能没有门）。每一分钟，Theseus 可以选择按下按钮使所有方块顺时针旋转 $90$ 度，或者向相邻的方块移动。只有当前方块 $A$ 与相邻方块 $B$ 分别有一扇通往对方的门时，Theseus 才能从 $A$ 移动到 $B$。 Theseus 找到了迷宫的入口，当前位置在第 $x_T$ 行第 $y_T$ 列的方块（记作 $(x_T, y_T)$）。他知道米诺陶藏在第 $x_M$ 行第 $y_M$ 列的方块（记作 $(x_M, y_M)$），想知道至少需要多少分钟才能到达那里。 Theseus 是个英雄，不是程序员，于是他向你寻求帮助。

输入的第一行为两个整数 $n$ 和 $m$（$1 \le n, m \le 1000$），分别表示迷宫的行数和列数。 接下来的 $n$ 行，每行包含 $m$ 个字符，描述了迷宫中每个方块的状态。可能的字符含义如下： - 「+」表示该方块有 $4$ 扇门（分别通向四个相邻方块）； - 「-」表示该方块有 $2$ 扇门，分别通向左右邻居； - 「|」表示该方块有 $2$ 扇门，分别通向上下邻居； - 「^」表示该方块有 $1$ 扇门，通向上方邻居； - 「>」表示该方块有 $1$ 扇门，通向右侧邻居； - 「

如果 Theseus 无法到达米诺陶的位置，则输出一行 -1。否则输出 Theseus 至少需要多少分钟才能到达米诺陶所在的方块。

假定 Theseus 在时间 $0$ 时刻位于 $(x_T, y_T)$ 方块。 由 ChatGPT 5 翻译