1197. 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

// BFS
inline int coordinates2id(int r, int c) {
    return r * 300 + c;
}
int minKnightMoves(int x, int y) {
    if (x == 0 && y == 0) return 0;
    vector<pair<int, int> > dirs({{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}});
    unordered_set<int> visited;
    queue<pair<int, int> > q({{0, 0}});
    visited.insert(coordinates2id(0, 0));
    int res = 0;
    while (!q.empty()) {
        ++res;
        for (int k = q.size() - 1; k >= 0; --k) {
            auto t = q.front(); q.pop();
            int r = t.first, c = t.second;
            for (const auto& dir : dirs) {
                int new_r = r + dir.first, new_c = c + dir.second;
                if (new_r == x && new_c == y) return res;
                if (visited.count(coordinates2id(new_r, new_c))) continue;
                if (x >= 0 && new_r < -1) continue;
                if (x <= 0 && new_r > 1) continue;
                if (y >= 0 && new_c < -1) continue;
                if (y <= 0 && new_c > 1) continue;
                q.push({new_r, new_c});
                visited.insert(coordinates2id(new_r, new_c));
            }
        }
    }
    return -1; // invalid
}

https://stackoverflow.com/questions/2339101/knights-shortest-path-on-chessboard/8778592#8778592

// Math
int minKnightMoves(int x, int y) { // time: O(1); space: O(1)
    // Axis Symmetry
    x = abs(x);
    y = abs(y);
    // Diagonal Symmetry
    if (x < y) swap(x, y);
    if (x == 1 && y == 0) return 3;
    if (x == 2 && y == 2) return 4;
    int delta = x - y;
    if (y > delta) {
        return (int)(delta - 2 * floor((float)(delta - y) / 3)); 
    } else {
        return (int)(delta - 2 * floor((delta - y) / 4));
    }
}