Catching the Krug

Let Krug start at $(r_K,c_K)$ and Doran start at $(r_D,c_D)$.

The big observation: Doran can move diagonally, so in one turn he can improve both row and column at the same time. Krug cannot. She only moves in one coordinate per turn. That is why this game collapses to a few distances to the border instead of some cursed minimax over a $10^9$ grid.

Useful escape directions

Krug can only build a real lead in a coordinate where she is already on one side of Doran.

For rows:

• If $r_D>r_K$, Doran is below Krug, so Krug can run upward.
• If $r_D<r_K$, Doran is above Krug, so Krug can run downward.
• If $r_D=r_K$, row escape gives nothing. Krug moving vertically once does not create a lasting row gap, because Doran moves immediately after her.

Columns are the same:

• If $c_D>c_K$, Krug can run left.
• If $c_D<c_K$, Krug can run right.
• If $c_D=c_K$, column escape gives nothing.

How long does one escape direction last?

Suppose $r_D>r_K$. Doran is below Krug, so Krug's row escape is upward.

Krug can spend $r_K$ moves reaching row $0$. After that, she cannot keep increasing the row distance. Doran still has to close the initial row gap $r_D-r_K$. So the total row-based survival clock is

$r_K+(r_D-r_K)=r_D.$

So if Doran is below Krug, candidate answer is $r_D$.

Similarly:

• If Doran is above Krug, row escape downward lasts $(n-r_K)+(r_K-r_D)=n-r_D.$
• If Doran is right of Krug, column escape left lasts $c_K+(c_D-c_K)=c_D.$
• If Doran is left of Krug, column escape right lasts $(n-c_K)+(c_K-c_D)=n-c_D.$

Why maximum, not sum?

This is the common wrong turn.

Krug might have both a row escape and a column escape, but she cannot cash them in one after another for free. While Krug spends a move on one coordinate, Doran can move diagonally and handle both coordinates at once. The escape clocks run in parallel.

So Krug chooses the escape direction with the latest deadline, and Doran's diagonal chase prevents combining deadlines.

Therefore:

$$ans=\max(\ [r_D>r_K]\cdot r_D,\ [r_D<r_K]\cdot(n-r_D),\ [c_D>c_K]\cdot c_D,\ [c_D<c_K]\cdot(n-c_D)\ ).$$

Directions whose condition is false are ignored.

There is never an infinite answer. The board is finite, and Doran's king movement eventually kills every escape route. Krug can stall; she cannot become immortal. Sad, but fair.

Algorithm

For each test case:

1. Start ans = 0.
2. Check the row relation between Doran and Krug and update with the valid row candidate.
3. Check the column relation and update with the valid column candidate.
4. Print ans.

Time complexity: $O(1)$ per test case.

Memory complexity: $O(1)$.