⚡Flashcard Drill➔
NeetCode #612LC-1197MediumGraphsNC Algo100
← Back to All Problems

#612 · #1197 · Minimum Knight Moves(进击的骑士)

📌 Problem Statement & Constraints

A knight moves on an infinite chessboard. Given x and y, return the minimum number of moves to reach (x, y) from (0, 0). Constraints: -300 <= x, y <= 300.

💡 Core Algorithmic Approaches

  1. BFS over the board, but the board is infinite -- so bound the search using symmetry and a margin.
  2. Symmetry: take x = abs(x) and y = abs(y), so the target is in the first quadrant.
  3. Bound the search to [-2, x+2] x [-2, y+2]: a shortest path never needs to go far outside.
  4. The margin of 2 is what allows the knight to go around when needed.

💻 Benchmark Python3 Implementation

class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        from collections import deque
        x, y = abs(x), abs(y)              # symmetry -> first quadrant
        moves = ((1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2))
        q = deque([(0, 0, 0)])
        seen = {(0, 0)}
        while q:
            r, c, d = q.popleft()
            if (r, c) == (x, y):
                return d
            for dr, dc in moves:
                nr, nc = r + dr, c + dc
                # a shortest path never needs to go more than 2 outside the box
                if -2 <= nr <= x + 2 and -2 <= nc <= y + 2 and (nr, nc) not in seen:
                    seen.add((nr, nc))
                    q.append((nr, nc, d + 1))
        return -1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(x * y): the bounded box has at most (x+5) * (y+5) cells.
💾 Space Complexity
O(x * y) for the visited set.

⚠️ Interview Pitfalls & Follow-ups

  • BFS on an unbounded board: it would never terminate.
  • Using 0 <= nr <= x as the bound: the knight sometimes must overshoot and come back, hence the margin of 2.
  • Forgetting the symmetry reduction: the box would be four times larger.
  • Assuming the knight can reach any cell in O(1): the BFS is needed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems