1197. Minimum Knight Moves

Posted on Edited on In

1197. Minimum Knight Moves

Description

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:

1
2
3
Input: x = 2, y = 1
Output: 1
Explanation: [0, 0] → [2, 1]

Example 2:

1
2
3
Input: x = 5, y = 5
Output: 4
Explanation: [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]

Constraints:

  • -300 <= x, y <= 300
  • 0 <= |x| + |y| <= 300

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    static constexpr int DIRs[8][2] = {{2, 1}, {2, -1}, {-2, 1}, {-2, -1},
                                       {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
    int minKnightMoves(int x, int y) {
        if (x == 0 && y == 0) {
            return 0;
        }
        vector<vector<bool>> visited(601, vector<bool>(601, false));
        x += 300;
        y += 300;
        queue<pair<int, int>> q;
        q.emplace(300, 300);
        visited[300][300] = true;
        int step = 1;
        while (true) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                auto [a, b] = q.front();
                q.pop();
                for (int j = 0; j < 8; j++) {
                    int dx = a + DIRs[j][0], dy = b + DIRs[j][1];
                    if (dx == x && dy == y) {
                        return step;
                    }
                    if (dx >= 0 && dx <= 600 && dy >= 0 && dy <= 600 && !visited[dx][dy]) {
                        visited[dx][dy] = true;
                        q.emplace(dx, dy);
                    }
                }
            }
            step++;
        }
        return -1;
    }
};