# BFS is still slow even if I use duque

Hi,

This is the problem I tried to solve:

Minimum Knight Moves

My solution was slow when I use a list to implement a queue. However, even when I use deque, the platform says that I exceed the time limit. Is there any way to improve the code? Thanks!

J

``````class Solution:
def minKnightMoves(self, x: int, y: int) -> int:
from collections import deque
visited = {(0, 0)}
# queue = [(0, 0)]
queue = deque([(0, 0)])
depth_map = {(0,0) : 0}
while queue:
# m = queue.pop(0)
m = queue.popleft()
for nbr in [(m+1, m+2), (m-1, m+2), (m+1, m-2), (m-1, m-2), (m+2, m+1), (m-2, m+1), (m+2, m-1), (m-2, m-1)]:
if nbr not in visited:
# queue += [nbr]
queue.append(nbr)
depth_map[nbr] = depth_map[m] + 1
if nbr == (x, y):
return depth_map[nbr]

``````

This is homework? We will help with hints and explainations but not solutions.

Try using coverage to find out where your code is spending its time.

``````python -m pip install coverage
``````

Can coverage do that? I thought it was just for analyzing test coverage. I can’t see anything in the docs about profiling support.

Python comes with a built-in profiler called `cProfile`.

These problems are meant to challenge you algorithmically.
Hints: Exploit symmetry. Use A-star if the problem allows it.

Doh! Yes you are right c profile is what you need!
Sorry for the confusion.

Try printing out each position visited. That might give you a hint.

In particular, print the knight moves going from `(0, 0)` to `(50, 100)`. Notice that most of the explored moves aren’t in the direction of the target.