1197. Minimum Knight Moves
https://leetcode.com/problems/minimum-knight-moves/
In an infinite chess board with coordinates from
-infinity to +infinity, you have a knight at square [0, 0].
A knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.
Return the minimum number of steps needed to move the knight to the square
[x, y]. It is guaranteed the answer exists.
Example 1:
Input: x = 2, y = 1 Output: 1 Explanation: [0, 0] → [2, 1]
Example 2:
Input: x = 5, y = 5 Output: 4 Explanation: [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]
Constraints:
|x| + |y| <= 300
---
Intuition
DFS will not work in infinite chessboard, if you start on a different direction on infinite chessboard, you will keep exploring wrong direction on infinite board to infinity
BFS is right choice for this problem
We can map the target into first quadrant because of symmetry of moves
x = Math.abs(x)
y = Math.abs(y)
Try all 8 moves from 0, 0 to target
Any move which lands at x == -1, y== -1 is allowed, but not -2 .. and so on.
From -1 next move can land us back into first quadrant
From -2.. onwards next move still lands outside of first quadrant so do not add such moves to the queue
Note - Use Set string to track visited instead of Set int[] since contains does not work right on array values
Also mark int[] as visited right when its added into the queue to prevent adding duplicates .. multiple positions on same array can add back same next position to next level, avoid that
---
Time - 8 ^ (m * n)
Space - 8 ^ (m * n)
---
Related problems
knight-on-chess-board
---
DFS will not work in infinite chessboard, if you start on a different direction on infinite chessboard, you will keep exploring wrong direction on infinite board to infinity
BFS is right choice for this problem
We can map the target into first quadrant because of symmetry of moves
x = Math.abs(x)
y = Math.abs(y)
Try all 8 moves from 0, 0 to target
Any move which lands at x == -1, y== -1 is allowed, but not -2 .. and so on.
From -1 next move can land us back into first quadrant
From -2.. onwards next move still lands outside of first quadrant so do not add such moves to the queue
Note - Use Set string to track visited instead of Set int[] since contains does not work right on array values
Also mark int[] as visited right when its added into the queue to prevent adding duplicates .. multiple positions on same array can add back same next position to next level, avoid that
---
Time - 8 ^ (m * n)
Space - 8 ^ (m * n)
---
Related problems
knight-on-chess-board
---
