1197.Minimum-Knight-Moves
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
ไปฃ็
Approach #1 BFS with pruning
Time: O(N) && Space: O(N)
class Solution {
private final int[][] DIRECTIONS = new int[][] {{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}};
public int minKnightMoves(int x, int y) {
// ๅไธช่ฑก้ๆนๅๆญฅๆฐๆฏไธๆ ท็
x = Math.abs(x);
y = Math.abs(y);
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] {0, 0});
Set<String> visited = new HashSet<>();
visited.add("0,0");
int result = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] cur = queue.remove();
int curX = cur[0];
int curY = cur[1];
if (curX == x && curY == y) {
return result;
}
for (int[] d: DIRECTIONS) {
int newX = curX + d[0];
int newY = curY + d[1];
// If you remove this condition newX >= -1 && newY >= -1) this solution would give TLE.
if (!visited.contains(newX + "," + newY) && newX >= -1 && newY >= -1) {
queue.add(new int[] {newX, newY});
visited.add(newX + "," + newY);
}
}
}
result++;
}
return -1;
}
}
Approach #2 DFS
class Solution {
public int minKnightMoves(int x, int y) {
Map<String, Integer> map = new HashMap<>();
// base case
map.put("0,0", 0);
map.put("1,0", 3);
map.put("1,1", 2);
map.put("2,0", 2);
return dfs(x, y, map);
}
private int dfs(int x, int y, Map<String, Integer> map) {
// Sysmetrical of axis
x = Math.abs(x);
y = Math.abs(y);
// Sysmetrical of diagonal
if (x < y) {
int temp = x;
x = y;
y = temp;
}
String s = x + "," + y;
if (map.containsKey(s)) return map.get(s);
int temp = Math.min(dfs(x-2, y-1, map),
dfs(x-1, y-2, map)) + 1;
map.put(s, temp);
return temp;
}
}
Last updated