Minimum Knight Moves

Leetcode 1197. Minimum Knight Moves

Problem

n 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:

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

Source: Leetcode 1197. Minimum Knight Moves

Solution

We can use Breadth First Search to solve this problem. But just applying BFS without any change will give you Time Limit Exceeded (TLE). We need a little optimization here.

The idea of optimization is simple. From point (0,0), the distance of (5,-3) should be same as that of (5,3). This is simple rule of symmetry. (If you find hard time understanding this, we would suggest use a graph paper and draw symmetrical points and check the distance)

So, we can simply avoid the negative values and make them positive by taking absolute values. This way, we reduce a huge lot of search space for BFS to go through and make its life much easier.

Here is the code below.

C++ Code

class Solution {
public:
    int minKnightMoves(int x, int y) {
        x = abs(x);
        y = abs(y);
        queue<pair<int, int>> q;
        q.push({0, 0});
        int steps = 0;
        vector<vector<int>> dir = { {2,-1}, {2,1}, {-2,-1}, {-2,1}, {1,2}, {1,-2}, {-1,2}, {-1,-2} };
        map<pair<int, int>, bool> visited;
        visited[make_pair(0, 0)] = true;
        
        while(!q.empty()){
            int len = q.size();
            for(int i = 0; i < len; i++){
                pair<int, int> cur = q.front();
                q.pop();
                if( (cur.first == x) && (cur.second == y) )
                        return steps;
                for(int j = 0; j < 8; j++){
                    int new_x = cur.first + dir[j][0];
                    int new_y = cur.second + dir[j][1];
                    new_x = abs(new_x);
                    new_y = abs(new_y);
                    if(!visited[make_pair(new_x, new_y)]){
                        visited[make_pair(new_x, new_y)] = true;
                        q.push(make_pair(new_x, new_y));
                    }
                }
            }
            steps++;
        }
        return 0;
    }
};

Conclusion

If you are confused with the solution, please let us know in the comment section! Happy Coding 🙂