On an n × n board, count how many distinct squares a knight can reach in at most
k moves starting from (startRow, startCol) (the start counts, reachable in 0 moves).
knightlyNumber(n, startRow, startCol, k)
Input format: n | startRow startCol | k.
n=8, start=(0,0), k=0 // → 1 (just the start)
n=8, start=(0,0), k=1 // → 3 (start + 2 knight moves)
n=3, start=(0,0), k=10 // → 8 (every square except the unreachable center)
A shortest-path/reachability question in disguise: treat every square as a node, with an edge between two squares a knight can jump between. "How many squares within at most k moves" becomes "how many nodes within distance k of the start."
Whenever a problem is about fewest moves or everything reachable within k steps, BFS is right — it explores in expanding rings of distance, fully finishing distance-d squares before touching distance-(d+1) ones. That means the BFS layer a square is discovered in directly tells you its move count, no extra bookkeeping needed since every move costs the same.
DFS would plunge deep along one sequence before backtracking, with no clean guarantee of finding the shortest path to a square before exploring further.
Start a queue with the starting square at distance 0, marked visited immediately (marking on enqueue prevents the same square being added multiple times via different paths). Repeatedly pop a square; if its distance hasn't hit the k-move limit, generate all eight knight moves. Unvisited, on-board results get marked visited, given distance one more than the current square's, and enqueued.
Every square marked visited is reachable within k moves or fewer — the final visited count (including the start, reachable in zero moves) is the answer.
Without marking on discovery, the same square could be enqueued repeatedly via different move sequences — blowing up runtime and double-counting. Marking on discovery guarantees each square is processed exactly once.
At most n² squares, each visited once, each generating up to eight moves to check — O(n²) time and space, independent of k, since BFS naturally stops once every reachable square is discovered.
def knightly_number(n, start_row, start_col, k):
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)]
count = 1
while len(queue) > 0:
r, c, d = queue.pop(0)
if d == k:
continue
for dr, dc in moves:
nr = r + dr
nc = c + dc
if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc]:
visited[nr][nc] = True
count += 1
queue.append((nr, nc, d + 1))
return count
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.