1197. Minimum Knight Moves

1197. Minimum Knight Moves (Medium)

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

Companies:
Expedia, Facebook, Amazon, Mathworks, Google, Indeed, Microsoft, Qualtrics, Cisco, Twitter

Related Topics:
Breadth-first Search

Solution 1. BFS with optimizations

Firstly, it's symmetric for axes. So let x = abs(x), y = abs(y).

Secondly, attempts with x or y values smaller than -1 should be ignored.

For example, to reach (1,1) from (0,0), the best way is to get (2,-1) or (-1,2) first, then (1,1) (two steps). If we eliminate all coordinates with negative numbers, then we can't reach (1,1) from (0,0) within two steps.

// OJ: https://leetcode.com/problems/minimum-knight-moves/
// Author: github.com/lzl124631x
// Time: O(XY)
// Space: O(XY)
class Solution {
public:
    int minKnightMoves(int x, int y) {
        x = abs(x);
        y = abs(y);
        queue<pair<int, int>> q;
        set<pair<int, int>> s;
        q.emplace(0, 0);
        s.emplace(0, 0);
        int ans = 0, dirs[8][2] = {{1, 2}, {1,-2}, {2,1},{2,-1},{-1,2},{-1,-2},{-2,1},{-2,-1}};
        while (q.size()) {
            int cnt = q.size();
            while (cnt--) {
                auto [a, b] = q.front();
                q.pop();
                if (a == x && b == y) return ans;
                for (auto &[dx, dy] : dirs) {
                    pair<int, int> next = {a + dx, b + dy};
                    if (abs(next.first) + abs(next.second) > 300 || next.first < -1 || next.second < -1 || s.count(next)) continue;
                    s.insert(next);
                    q.push(next);
                }
            }
            ++ans;
        }
        return 0;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/minimum-knight-moves/
// Author: github.com/lzl124631x
// Time: O(1)
// Space: O(1)
// Ref: https://leetcode.com/problems/minimum-knight-moves/discuss/682850/C%2B%2B-O(1)-Formula-solution-with-plot-explanation
class Solution {
public:
    int minKnightMoves(int x, int y) {
        x = abs(x);
        y = abs(y);
        if (x < y) swap(x, y);
        if (x == 1 and y == 0) return 3;
        if (x == 2 and y == 2) return 4;
        if (y <= x / 2) {
            return (x + 1) / 2 + (x / 2 - y) % 2;
        }
        return (x + y) / 3 + (x + y) % 3; 
    }
};