Hi,
This is the problem I tried to solve:
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[0]+1, m[1]+2), (m[0]-1, m[1]+2), (m[0]+1, m[1]-2), (m[0]-1, m[1]-2), (m[0]+2, m[1]+1), (m[0]-2, m[1]+1), (m[0]+2, m[1]-1), (m[0]-2, m[1]-1)]:
if nbr not in visited:
visited.add(nbr)
# queue += [nbr]
queue.append(nbr)
depth_map[nbr] = depth_map[m] + 1
if nbr == (x, y):
return depth_map[nbr]