-
Notifications
You must be signed in to change notification settings - Fork 0
LC 1197 [M] Minimum Knight Moves
Code with Senpai edited this page Feb 15, 2022
·
1 revision
DIRS = [(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)]
class Solution:
def minKnightMoves(self, x: int, y: int) -> int:
Q = deque([ (0,0) ])
seen = set()
seen.add( (0,0) )
# limit top right corner so we can check the bounds and not worry about other positions cause they are symmetric (board is symmetric)
x = abs(x)
y = abs(y)
steps = 0
while Q:
for _ in range(len(Q)):
r, c = Q.popleft()
if r == x and c == y:
return steps
for dr, dc in DIRS:
nr = r + dr
nc = c + dc
# extend bounds by 2 to let the knight jump off by offset 2 so it can jump back
if (nr, nc) not in seen and -2 <= nr <= x + 2 and -2 <= nc <= y + 2:
Q.append( (nr, nc) )
seen.add( (nr, nc) )
steps += 1
footer