暂无测试数据。

U538592 漩涡迷宫(matrix)

题目描述

【问题描述】

小明是一位勇敢的探险家，他正在探索一座神秘的迷宫。迷宫的结构非常独特，呈环形排列，宛如一个迷宫的漩涡。每个房间都有一个数字表示。

具体而言，下面是一个$4 \times 5$大小的迷宫矩阵：

1	2	3	4	5
14	15	16	17	6
13	20	19	18	7
12	11	10	9	8

房间的编号是一个顺时针的环形排列。

小明目前身处房间$x$，他想知道距离他最近的目标房间$y$有多远。我们可以使用曼哈顿距离来计算。

曼哈顿距离就像在这个迷宫中探险，最少需要经过多少个房间才能从一个房间到达另一个房间。假设房间$x$是位于第$a_1$行第$b_1$列 ，房间$y$位于第$a_2$行第$b_2$列，那么这两个房间间的曼哈顿距离为$|a_1 - a_2| + |b_1 - b_2|$。其中$|x|$表示$x$的绝对值。

输入格式

第一行包含一个正整数$T$，表示测试数据的组数。

接下来$T$行，每行是一组测试数据，包含四个正整数$n、m、x、y$，表示迷宫的行、列以及小明所处的房间号和目标房间号。

输出格式

输出$T$行，每行包含一个整数，表示对应测试数据小明到目标房间的曼哈顿距离。

输入输出样例 #1

输入 #1

2
4 5 20 17
4 5 20 18

输出 #1

3
2

说明/提示

【样例1解释】

$4 \times 5$的迷宫如题意所示。 小明所在的房间20位于第3行第2列，目标房间17位于第2行第4列，它们的曼哈顿距离为$|3 - 2| + |2 - 4| = 1 + 2 = 3$。

【数据范围】

对于30%的数据，满足$T \leq 10, n \leq 10^{5}, m \leq 10^{5}, n \times m \leq 10^{5}$。 对于另外40%的数据，满足$T \leq 5, n \leq 10^{6}, m \leq 10^{6}$。 对于100%的数据，满足$T \leq 10^{4}, n \leq 10^{18}, m \leq 10^{18}, n \times m \leq 10^{18}, x \leq 10^{18}, y \leq 10^{18}$。