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).
Definition
- Class:
- Knishop
- Method:
- getShortestPath
- Parameters:
- int, int, int, int
- Returns:
- int
- Method signature:
- int getShortestPath(int x1, int y1, int x2, int y2)
- (be sure your method is public)
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.
Examples
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
63
58
69
49
Returns: 2
-81
-53
-37
-49
Returns: 2
-7
88
96
89
Returns: 2
96
-6
-95
24
Returns: 3
-60
81
-18
-48
Returns: 3
90
-61
98
-77
Returns: 2
-19
15
86
70
Returns: 2
63
-75
-64
-54
Returns: 2
32
-23
20
-34
Returns: 2
-35
-40
-7
63
Returns: 3
50
-97
58
-96
Returns: 3
-83
-1
-6
-90
Returns: 2
-82
-16
69
-20
Returns: 3
-1
-5
-50
-3
Returns: 3
-75
-1
1
53
Returns: 2
71
-83
15
44
Returns: 3
-66
27
87
22
Returns: 2
-79
-72
44
-57
Returns: 2
786121129
332947394
-535708243
324234921
Returns: 3
-214495340
774765455
215931966
951230889
Returns: 2
-742295552
268052769
340643457
555301901
Returns: 3
232188328
43190550
388681622
-646098993
Returns: 3
-283755856
378592217
-170280232
783725839
Returns: 2
155771345
676050565
-340426592
-268364988
Returns: 2
-396973153
-159362725
-228208158
-140781301
Returns: 3
-116695744
327976847
-779210653
-757829514
Returns: 2
596752325
44771082
-846332168
-537110377
Returns: 2
965648387
597491272
236495590
157107352
Returns: 3
-685373142
-352833994
445628749
-43666168
Returns: 3
-985694425
261825902
-790588295
-14977798
Returns: 2
779614374
129363402
-864165753
402005613
Returns: 2
-441706353
-622885432
-608945831
-791834869
Returns: 3
219578947
-870382254
797111886
251243891
Returns: 2
-589453394
480885383
-82606636
-547098002
Returns: 3
-578343795
919966263
129779342
444733620
Returns: 2
-1130608
-539586383
-113775312
658825542
Returns: 3
-408888129
-692407952
342854109
-725037198
Returns: 2
-242202620
-208932250
474897665
-880888199
Returns: 2
5
-100000001
-99999997
-99999995
Returns: 2
100000000
-100000002
99999996
100000003
Returns: 3
99999998
3
5
-99999998
Returns: 2
-100000004
99999995
0
-100000001
Returns: 2
-100000003
-99999999
1
1
Returns: 2
99999998
-5
-3
0
Returns: 2
-5
-5
2
-99999999
Returns: 3
100000004
-100000001
5
-100000003
Returns: 3
1
-3
-99999998
100000005
Returns: 3
-3
3
-99999997
0
Returns: 3
100000005
2
-99999997
-5
Returns: 3
-5
99999998
-1
-5
Returns: 3
-100000001
-3
100000001
-100000002
Returns: 3
100000002
-1
-100000001
-100000005
Returns: 3
100000005
99999995
-99999996
100000005
Returns: 3
-4
-100000001
4
-100000004
Returns: 3
-100000003
100000002
99999997
3
Returns: 3
100000004
-99999996
100000004
5
Returns: 3
99999995
1
-100000004
99999999
Returns: 3
100000001
100000003
0
-100000003
Returns: 3
2
2
2
2
Returns: 0
0
0
-1000000000
-1000000000
Returns: 1
0
0
-1000000000
1000000000
Returns: 1
0
0
1000000000
-1000000000
Returns: 1
0
0
1000000000
1000000000
Returns: 1
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).
1
1
1
1
Returns: 0
1
1000000000
-1
-999999998
Returns: 2
0
0
0
1
Returns: 2
0
0
500
999
Returns: 3
0
0
1
2
Returns: 1
-99
-100
90001
900
Returns: 2
1
0
0
0
Returns: 2
-99
-100
9000001
900
Returns: 2
999999895
-999999919
999999839
999999805
Returns: 2
1
1000000000
-1
-1
Returns: 3
999999888
99
-999999897
-999999878
Returns: 2
1000000000
100000000
99999999
0
Returns: 3
1
1000000000
-1
-999998
Returns: 2
0
0
80
40
Returns: 2
-100
-99
900
9001
Returns: 2