Robot Cleaner 2

机器人清洁器 2

时间限制： 1.0 秒 内存限制： 256 MB

---

题目描述

一个清洁机器人被放置在一个长方形房间的地板上，房间四周由墙壁围住。

地板由 (n) 行、(m) 列组成。

地板的行按照从上到下的顺序编号为：

$$1,2,\ldots,n$$

地板的列按照从左到右的顺序编号为：

$$1,2,\ldots,m$$

第 (r) 行与第 (c) 列交叉处的格子记作：

$$(r,c)$$

机器人最初位于：

$$(r_b,c_b)$$

---

每经过 1 秒，机器人会移动 (dr) 行、(dc) 列。

也就是说，如果机器人当前位于：

$$(r,c)$$

那么 1 秒之后，它会移动到：

$$(r+dr,\ c+dc)$$

最开始：

$$dr=1,\qquad dc=1$$

也就是说，机器人最初朝右下方移动。

如果机器人即将移动的方向上存在一面竖直墙壁（即左侧墙壁或右侧墙壁），那么在移动之前，它在水平方向上的运动方向会发生反射，即：

$$dc\leftarrow -dc$$

类似地，如果机器人即将移动的方向上存在一面水平墙壁（即上侧墙壁或下侧墙壁），那么在移动之前，它在竖直方向上的运动方向会发生反射，即：

$$dr\leftarrow -dr$$

然后机器人再按照新的 ((dr,dc)) 进行移动。

---

每一秒，包括机器人开始移动之前的初始时刻，机器人都会清洁：

与机器人当前位置处于同一行或同一列的所有格子。

机器人的任务是清洁整个地板。

也就是说：

地板上的每一个格子都必须至少被清洁一次。

---

【图片位置 1】

图片说明：

该图展示了第一个样例。 红色弧线表示机器人。 绿色格子表示已经被清洁的格子。 每一秒，机器人都会清洁其当前位置所在的一整行和一整列。

---

给定地板的尺寸 (n,m)，以及机器人的初始位置：

$$(r_b,c_b)$$

请计算机器人完成清洁整个地板这一任务所需要的时间。

---

输入格式

每个输入文件包含多组测试数据。

第一行包含一个整数：

$$t$$

表示测试用例的数量，其中：

$$1\le t\le 10^4$$

接下来是各个测试用例。

每个测试用例仅包含一行，包含 4 个整数：

$$n,\ m,\ r_b,\ c_b$$

满足：

$$2\le n,m\le100$$ $$1\le r_b\le n$$ $$1\le c_b\le m$$

其中：

• (n)：房间地板的行数；
• (m)：房间地板的列数；
• (r_b)：机器人初始所在的行；
• (c_b)：机器人初始所在的列。

---

输出格式

对于每一个测试用例，输出一个整数：

机器人清洁完整个地板所需要的时间。

可以证明，最终地板上的每一个格子都会至少被清洁一次。

---

评分

本题总分为：

$$500$$

分。

---

样例输入 1

5
10 10 6 1
10 10 9 9
9 8 5 6
6 9 2 2
2 2 1 1

样例输出 1

9
10
9
9
1

---

样例说明

样例 1

在第一个样例中，地板大小为：

$$10\times10$$

机器人的初始位置为：

$$(6,1)$$

请参考题目描述中的示意图。

也就是前面：

【图片位置 1】

所对应的动画。

---

样例 2

在第二个样例中，地板大小仍然为：

$$10\times10$$

但是机器人的初始位置变为：

$$(9,9)$$

【图片位置 2】

---

样例 3

在第三个样例中，地板大小为：

$$9\times8$$

机器人的初始位置为：

$$(5,6)$$

【图片位置 3】

---

样例 4

在第四个样例中，地板大小为：

$$6\times9$$

机器人的初始位置为：

$$(2,2)$$

【图片位置 4】

---

样例 5

在最后一个样例中，地板大小为：

$$2\times2$$

机器人的初始位置为：

$$(1,1)$$

【图片位置 5】

---

这个版本已经把你之前网页机器翻译中丢失的几个关键公式恢复出来了，尤其是：

初始：
dr = 1
dc = 1

以及撞墙时：

竖直墙：
dc = -dc

水平墙：
dr = -dr

所以机器人一开始确实是朝右下方向运动。

测试点编号	难度层级	用例数	数据范围	特殊性质	主要覆盖点
1	弱数据	8	n,m ≤ 5	最小规模、单维长度为 1	零输出、首尾位置、基础分支
2	弱数据 / 边界		n,m ≤ 100	pos=1、pos=len、长宽不等	首位特判、行列方向互换
3	正常数据	10		内部位置、对称用例	行更小、列更小、两者相等
4	正常 / 强边界		n,m ≤ 10⁶	pos=2、len-1、极端长宽比	off-by-one、结果相差 1、小维度决定答案
5	极限数据	12	n,m ≤ 10⁹	大数、首尾、中间位置	64 位运算、接近 2×10⁹ 的结果