---
description: BFS
---

# Minimum Knight Moves

## Problem

![](https://1063826111-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MGdx41c9p2PMgIHbUTK%2F-MRLZFzdg-ebMbJovtS2%2F-MRL_RSyAL5K2TrFEdK7%2FScreen%20Shot%202021-01-18%20at%2010.40.46%20AM.png?alt=media\&token=0981891c-52d0-44ad-8552-00c3dfa14e2a)

![](https://1063826111-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MGdx41c9p2PMgIHbUTK%2F-MRLZFzdg-ebMbJovtS2%2F-MRL_XQJKA7xcNHXIVun%2FScreen%20Shot%202021-01-18%20at%2010.41.11%20AM.png?alt=media\&token=35be9700-556f-4066-9d00-445a46be7c52)

### Thought Process

*   We care about the levels in this problem


*   Infinite chess board meaning no boundaries&#x20;


* BFS to look at all the neighbors&#x20;

![](https://1063826111-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MGdx41c9p2PMgIHbUTK%2F-MRLZFzdg-ebMbJovtS2%2F-MRL_xzE05MWEZjeBK-q%2FIMG_BE888B202974-1.jpeg?alt=media\&token=33596786-7363-47b6-8cec-0df87f6112f9)

## Solution

```
from collections import deque

class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        q = deque()
        visited = set((0,0))
        q.append([0,0])
        steps = 0
        direc = [[-2,-1], [-2,1],[2,-1],[2,1],[-1,-2], [1,-2], [-1,2], [1,2]]
        x = abs(x)
        y = abs(y)
        
        while q:
            levelSize = len(q)
            for _ in range(levelSize):
                coor = q.popleft()
                xCoor = coor[0]
                yCoor = coor[1]
                
                if xCoor == x and yCoor == y:
                    return steps
                
                else:
                    for i in direc:
                        newX = xCoor + i[0]
                        newY = yCoor + i[1]
                
                        if (newX, newY) not in visited and (newX>=-2 and newY >= -2):
                
                            q.append([newX,newY])
                            visited.add((newX, newY))
            steps+=1 
            
```

## Time Complexity:

* **Time**: O(n) where n is the number of moves we have to make
* **Space:** O(n) where n is the number of moves we have to make
