1142. Minimum Knight Moves

• Difficulty: Medium

• Topics: Breadth-first Search

• Similar Questions:

Problem:

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

Solutions:

class Solution {
public:
    int minKnightMoves(int x, int y) {
        set<pair<int, int>> visited;
        queue<pair<int, int>> q;
        q.push({0, 0});

        int level = 0;
        while (!q.empty()) {
            int size = q.size();
            for (int n = 0; n < size; ++n) {
                auto pos = q.front(); q.pop();
                if (abs(pos.first) == abs(x) && abs(pos.second) == abs(y))  return level;
                if (visited.count({abs(pos.first), abs(pos.second)})) continue;
                visited.insert({abs(pos.first), abs(pos.second)});
                for (int i = 0; i < 8; ++i) {
                    q.push({pos.first + directions[i][0], pos.second + directions[i][1]});
                }
            }
            ++level;
        }
        return -1;
    }


private:
    int directions[8][2] = {
        {1, 2}, 
        {2, 1},
        {2, -1},
        {1, -2},
        {-1, -2},
        {-2, -1},
        {-2, 1},
        {-1, 2}
    };
};