# 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`
###### 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];
int new_y = cur.second + dir[j];
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 🙂