Description

Submission

class Solution {

public:
    int minKnightMoves(int x, int y) {
        vector<pair<int, int>> dirs = {{1, 2}, {1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {-1, 2}, {-1, -2}};
        
        queue<pair<int, int>> q;
        int offset = 5;
        x = abs(x) + offset;
        y = abs(y) + offset;
        int n = max(x, y) + offset;
        vector<vector<int>> dp(n, vector<int>(n, INT_MAX / 2));
        vector<vector<int>> visited(n, vector<int>(n, 0));
        
        q.push({x, y});
        dp[x][y] = 0;
        while(!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            
            if(visited[x][y]) continue;
            visited[x][y] = 1;
            
            for(auto [dx, dy]: dirs) {
                int newX = x + dx;
                int newY = y + dy;
                if(newX < 0 || newY < 0 || newX >= n || newY >= n) continue;
                if(visited[newX][newY]) continue;
                if(dp[newX][newY] > dp[x][y] + 1) {
                    dp[newX][newY] =  dp[x][y] + 1;
                    q.push({newX, newY});
                }
            }
        }
        
        return dp[offset][offset];
    }
};