Knishop
2018 TCO Argentina Fun · 2018-04-20 · by majk
Problem Statement
Knishop is a long-forgotten chess piece. In each move, the player can choose whether to move the knishop as a knight or as a bishop. This ability was deemed too powerful and so the piece was banned. But today you are lucky, as you will get the rare chance to play with the knishop.
In any single single move:
- A bishop can move by any number of squares in one of the four diagonal directions.
- A knight can move by two squares horizontally and one vertically, or by two squares vertically and one horizontally. (Thus, the move of a knight resembles the letter 'L'.)
- A knishop can move like a bishop or like a knight.
You are given a knishop on an infinite chessboard. The knishop is located at (x1, y1). Compute and return the smallest number of moves in which it is possible to move the knishop to (x2, y2).
Constraints
- x1 will be between -109 and 109, inclusive.
- y1 will be between -109 and 109, inclusive.
- x2 will be between -109 and 109, inclusive.
- y2 will be between -109 and 109, inclusive.
0 0 2 3 Returns: 2
We want to move this knishop from (0, 0) to (2, 3). One optimal solution is to move it like a knight from (0, 0) to (-2, -1), and then like a bishop from (-2, -1) to (2, 3).
5 2 7 0 Returns: 1
Both (5, 2) and (7, 0) lie on the same diagonal, hence the optimal solution requires just a single move (in which the knishop moves like a bishop).
918273645 987654321 123456789 123456798 Returns: 3
-16 -90 10 86 Returns: 2
-91 -61 -41 13 Returns: 2
42 47 42 47 Returns: 0
If the destination is the same as the current cell, no moves are needed.
10 10 14 8 Returns: 2
One optimal solution is to jump like a knight twice: (10, 10) to (12, 9) to (14, 8). Another optimal solution is to move like a bishop twice: (10, 10) to (11, 11) to (14, 8).
Submissions are judged against all 85 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Knishop with a public method int getShortestPath(int x1, int y1, int x2, int y2) · 85 test cases · 2 s / 256 MB per case