On an n × n chessboard, a knight starts at (startRow, startCol). Return the minimum
number of knight moves to reach (targetRow, targetCol), or -1 if unreachable. A
knight moves in an L: ±1/±2 or ±2/±1.
knightAttack(n, startRow, startCol, targetRow, targetCol)
Input format: n | startRow startCol | targetRow targetCol.
n=8, start=(0,0), target=(1,2) // → 1
n=8, start=(0,0), target=(2,2) // → 4 (the famous "two squares diagonal" case)
n=8, start=(0,0), target=(0,0) // → 0
You want the minimum number of moves, where every move costs the same one unit. Whenever a problem asks for fewest steps in a graph with equally-weighted edges, that's the signal to reach for breadth-first search, not DFS or greedy jumping toward the target.
Greedily picking the knight move that looks geometrically closest doesn't work — a knight's movement is irregular, and the move that looks closest in straight-line distance isn't necessarily part of the shortest sequence, since the knight can only land on specific offset squares. Greedy choices can dead-end or lengthen the path.
Model the board as a graph: each square is a node, with an edge between two squares a knight can jump directly between (up to eight moves from any square). Fewest moves between two nodes in an unweighted graph is exactly what BFS finds.
BFS explores in layers ordered by distance from the start: everything reachable in one move, then two, and so on. The first time you reach the target, you're guaranteed to have found it via the shortest path — no later layer could represent a shorter one.
Without a visited set, the same square could be re-enqueued from multiple directions, wasting work and potentially reporting a longer distance after a shorter one was already found. Marking a square visited the moment it's discovered keeps its recorded distance equal to the true shortest distance.
def knight_attack(n, start_row, start_col, target_row, target_col):
moves = [(1, 2), (2, 1), (-1, 2), (-2, 1), (1, -2), (2, -1), (-1, -2), (-2, -1)]
visited = [[False] * n for _ in range(n)]
visited[start_row][start_col] = True
queue = [(start_row, start_col, 0)]
while queue:
r, c, d = queue.pop(0)
if r == target_row and c == target_col:
return d
for dr, dc in moves:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc]:
visited[nr][nc] = True
queue.append((nr, nc, d + 1))
return -1
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.