题目描述

给你一个可以用 $n \times m$ 的网格表示的房间。一个小球位于位置 $(i_1, j_1)$（第 $i_1$ 行第 $j_1$ 列的交点），并以四个对角方向之一开始运动：

• 小球向右下方运动，记作 $\texttt{DR}$，表示每走一步，小球的位置从 $(i, j)$ 变为 $(i+1, j+1)$。
• 小球向左下方运动，记作 $\texttt{DL}$，表示每走一步，小球的位置从 $(i, j)$ 变为 $(i+1, j-1)$。
• 小球向右上方运动，记作 $\texttt{UR}$，表示每走一步，小球的位置从 $(i, j)$ 变为 $(i-1, j+1)$。
• 小球向左上方运动，记作 $\texttt{UL}$，表示每走一步，小球的位置从 $(i, j)$ 变为 $(i-1, j-1)$。

每走一步后，小球会保持原有的方向，除非它撞到墙壁（即下一步会超出房间边界）。在这种情况下，小球的运动方向会沿着撞到的墙的轴翻转；如果小球撞到角落，则两个方向都会翻转。每次发生这种情况称为一次“反弹”。小球永远不会停止运动。

在上面的例子中，小球从 $(1, 7)$ 开始，沿着 $\texttt{DL}$ 方向运动，直到到达底部墙壁，然后反弹并沿着 $\texttt{UL}$ 方向继续运动。到达左侧墙壁后，小球反弹并沿着 $\texttt{UR}$ 方向继续运动。当小球到达上侧墙壁时，反弹并沿着 $\texttt{DR}$ 方向继续运动。到达右下角后，小球反弹一次并沿着 $\texttt{UL}$ 方向继续运动，依此类推。

你的任务是计算小球在到达房间内的 $(i_2, j_2)$ 这个格子前，会经历多少次反弹；如果小球永远无法到达该格子，则输出 $-1$。

注意，小球会先进入一个格子，然后如果需要再发生反弹。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。

每个测试用例的第一行包含六个整数和一个字符串 $n, m, i_1, j_1, i_2, j_2, d$（$2 \leq n, m \leq 25000$；$1 \leq i_1, i_2 \leq n$；$1 \leq j_1, j_2 \leq m$；$d \in \{\texttt{DR}, \texttt{DL}, \texttt{UR}, \texttt{UL}\}$），分别表示网格的行数和列数、小球的起始坐标、目标坐标以及小球的初始运动方向。

保证所有测试用例中 $n \cdot m$ 的总和不超过 $5 \times 10^4$。

输出格式

对于每个测试用例，输出一个整数，表示小球首次到达 $(i_2, j_2)$ 之前经历的反弹次数；如果小球永远无法到达该格子，则输出 $-1$。

样例

6
5 7 1 7 2 4 DL
5 7 1 7 3 2 DL
3 3 1 3 2 2 UR
2 4 2 1 2 2 DR
4 3 1 1 1 3 UL
6 4 1 2 3 4 DR

3
-1
1
-1
4
0

样例说明

由 ChatGPT 4.1 翻译

来源

Codeforces 1807F，英文题名 Bouncy Ball。