Robot Cleaner
Contest: Codeforces Round 763 (Div. 2)
Difficulty rating: 800
Tags: brute force, implementation, math

A robot cleaner is placed on the floor of a rectangle room, surrounded by walls. The floor consists of $$$n$$$ rows and $$$m$$$ columns. The rows of the floor are numbered from $$$1$$$ to $$$n$$$ from top to bottom, and columns of the floor are numbered from $$$1$$$ to $$$m$$$ from left to right. The cell on the intersection of the $$$r$$$-th row and the $$$c$$$-th column is denoted as $$$(r,c)$$$. The initial position of the robot is $$$(r_b, c_b)$$$.

In one second, the robot moves by $$$dr$$$ rows and $$$dc$$$ columns, that is, after one second, the robot moves from the cell $$$(r, c)$$$ to $$$(r + dr, c + dc)$$$. Initially $$$dr = 1$$$, $$$dc = 1$$$. If there is a vertical wall (the left or the right walls) in the movement direction, $$$dc$$$ is reflected before the movement, so the new value of $$$dc$$$ is $$$-dc$$$. And if there is a horizontal wall (the upper or lower walls), $$$dr$$$ is reflected before the movement, so the new value of $$$dr$$$ is $$$-dr$$$.

Each second (including the moment before the robot starts moving), the robot cleans every cell lying in the same row or the same column as its position. There is only one dirty cell at $$$(r_d, c_d)$$$. The job of the robot is to clean that dirty cell.

Illustration for the first example. The blue arc is the robot. The red star is the target dirty cell. Each second the robot cleans a row and a column, denoted by yellow stripes.

Given the floor size $$$n$$$ and $$$m$$$, the robot's initial position $$$(r_b, c_b)$$$ and the dirty cell's position $$$(r_d, c_d)$$$, find the time for the robot to do its job.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). Description of the test cases follows.

A test case consists of only one line, containing six integers $$$n$$$, $$$m$$$, $$$r_b$$$, $$$c_b$$$, $$$r_d$$$, and $$$c_d$$$ ($$$1 \le n, m \le 100$$$, $$$1 \le r_b, r_d \le n$$$, $$$1 \le c_b, c_d \le m$$$) — the sizes of the room, the initial position of the robot and the position of the dirt cell.

Output format:
For each test case, print an integer — the time for the robot to clean the dirty cell. We can show that the robot always cleans the dirty cell eventually.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, the floor has the size of $$$10\times 10$$$. The initial position of the robot is $$$(6, 1)$$$ and the position of the dirty cell is $$$(2, 8)$$$. See the illustration of this example in the problem statement.

In the second example, the floor is the same, but the initial position of the robot is now $$$(9, 9)$$$, and the position of the dirty cell is $$$(1, 1)$$$. In this example, the robot went straight to the dirty cell and clean it.

In the third example, the floor has the size $$$9 \times 8$$$. The initial position of the robot is $$$(5, 6)$$$, and the position of the dirty cell is $$$(2, 1)$$$.

In the fourth example, the floor has the size $$$6 \times 9$$$. The initial position of the robot is $$$(2, 2)$$$ and the position of the dirty cell is $$$(5, 8)$$$.

In the last example, the robot was already standing in the same column as the dirty cell, so it can clean the cell right away.

Example input:
5
10 10 6 1 2 8
10 10 9 9 1 1
9 8 5 6 2 1
6 9 2 2 5 8
2 2 1 1 2 1

Example output:
7
10
9
3
0

Editorial:
Let's consider the 1-D problem of this problem: there are $$$n$$$ cells, lying in a row. The robot is at the $$$x$$$-th cell, and the dirty cell is at the $$$y$$$-th cell. Each second, the robot cleans the cell at its position. The robot initially moves by 1 cell to the right each second. If there is no cell in the movement direction, its direction will be reflected. What is the minimum time for the robot to clean the dirty cell?
There are two cases needed to be considered:
• If $$$x \le y$$$, then the answer is $$$y - x$$$. The robot just goes straight to the dirty cell.
• Otherwise, if $$$x > y$$$, then the robot needs to go to the right endpoint first, and then go back to the dirty cell. Going to the right endpoint takes $$$n - x$$$ seconds, and going from that cell to the dirty cell takes $$$n - y$$$ seconds. Therefore, the answer for this case is $$$2 \cdot n - x - y$$$.
Going back to our original problem, we can solve it by dividing it into two 1-D versions. This is done by projecting the position of the robot and the dirty cell onto the $$$Ox$$$ and $$$Oy$$$ axis as follows.
By doing so, we can see that we can clean the dirty cell, if and only if one of the projections of the robot can reach the dirty cell. Therefore, the answer is the minimum between the answers of the two sub-problems.