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:


Solution:

class Solution {
    static class Pair {
        int x;
        int y;
        
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
        
        @Override
        public boolean equals(Object o) {
            Pair p = (Pair) o;
            return p.x == this.x && p.y == this.y;
        }
        
        @Override
        public int hashCode() {
            int h = 17;
            h = 37 * h + x;
            h = 37 * h + y;
            return h;
        }
        
        public double distance(Pair p) {
            return Math.sqrt((p.x - x) * (p.x - x) + (p.y - y) * (p.y - y));
        }
    }
    
    public int minKnightMoves(int x, int y) {
        int[] dx = new int[]{-2,-1,1,2,2,1,-1,-2};
        int[] dy = new int[]{1,2,2,1,-1,-2,-2,-1};
        Set<Pair> visited = new HashSet();
        Queue<Pair> queue = new ArrayDeque();
        Pair start = new Pair(0, 0);
        queue.offer(start);
        visited.add(start);
        Pair target = new Pair(x, y);
        int step = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i ++) {
                Pair curr = `queue.poll();
                if (curr.equals(target)) {
                    return step;
                }
                for (int j = 0; j < 8; j ++) {
                    int nx = curr.x + dx[j];
                    int ny = curr.y + dy[j];
                    Pair next = new Pair(nx, ny);
                    if ((curr.distance(target) < 2 || next.distance(target) <= curr.distance(target)) && visited.add(next)) {
                        queue.offer(next);
                    }
                }
            }
            step ++;
        }
        return -1;
    }
}