BISHOPMV - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

There’s a bishop on an 8\times 8 chessboard, at cell (X_1, Y_1). It wants to reach (X_2, Y_2).
Find the minimum number of moves needed to do so, if it is even possible.

EXPLANATION:

Let’s color the cell (X, Y) white if X+Y is even, and black otherwise.
This is just chessboard coloring.

A bishop that starts on a white cell can only move to other white cells and cannot ever reach a black cell.
However, it is able to reach every white cell.

Similarly, a bishop that starts on a black cell can reach every black cell but no white cell.

So, if (X_1, Y_1) and (X_2, Y_2) are of different colors, the bishop cannot reach the second cell from the first.

Now, assume (X_1, Y_1) and (X_2, Y_2) are the same color.
The bishop can certainly reach the target square so we only need to find the minimum moves needed.
This can be done as follows:

  • If X_1-Y_1 = X_2-Y_2 then the two cells lie on the same diagonal (going top-left to bottom-right).
    In this case, one move is enough.
  • Similarly, if X_1+Y_1 = X_+Y_2 then the two cells lie on the same diagonal (going top-right to bottom-left), so again one move is enough.
  • If the above two cases fail, two moves are needed: one along each diagonal.

So, quite simply:

  • If X_1+Y_1 and X_2+Y_2 have different parities, the answer is -1.
  • If X_1+Y_1 = X_2+Y_2 or X_1-Y_1 = X_2-Y_2 then the answer is 1.
  • Otherwise, the answer is 2.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    x1, y1, x2, y2 = map(int, input().split())
    
    if (x1+y1)%2 != (x2+y2)%2: print(-1)
    else:
        if (x1+y1 == x2+y2) or (x1-y1 == x2-y2): print(1)
        else: print(2)
2

I wrote this one too the same. I hope i wont get plagarised.