LeetCode [1197] Minimum Knight Moves

 1197. Minimum Knight Moves

Medium

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

class Solution { Map<String, Integer> map = new HashMap<>(); public int minKnightMoves(int x, int y) { x = Math.abs(x); y = Math.abs(y); if(x+y==0) return 0; if(x+y==2) return 2; String key = x+":"+y; // System.out.println(key); if(!map.containsKey(key)){ int a = minKnightMoves(x-1, y-2); int b = minKnightMoves(x-2, y-1); map.put(key, Math.min(a,b)+1); } return map.get(key); } }