A grid has open cells (O), walls (X), and carrots (C). Starting from
(startRow, startCol), return the length of the shortest path (number of steps,
moving up/down/left/right through non-wall cells) to the nearest carrot. If no
carrot is reachable, return -1.
closestCarrot(grid, startRow, startCol)
Input format: grid | startRow startCol, grid rows separated by |.
(OOO|OXO|OOC) from (0,0) // → 4
(OO|OO) from (0,0) // → -1 (no carrots)
(C) from (0,0) // → 0
Strip away the grid dressing and this is the same shortest-path question: fewest steps from a start to some target, where every step costs the same. Whenever every move costs the same, BFS is the right tool — it explores outward in rings of increasing distance, guaranteeing the first time you reach any target, it's via the shortest route.
Earlier you searched for one specific destination. Here, any carrot cell counts, and you want the closest. This needs almost no change to BFS: since it visits cells in strict order of increasing distance, the very first carrot cell it dequeues is guaranteed closest — everything closer has already been checked and found not to be a carrot.
Each cell is a node connected to its up/down/left/right neighbours, but walls can't be moved into at all — they should never be enqueued, as if they and their edges don't exist.
Just as with general shortest path, marking a cell visited the moment it's enqueued (not when processed) prevents it being queued multiple times via different routes, which would waste work and risk the wrong recorded distance. This is what keeps the ring-by-ring guarantee intact.
from collections import deque
def closest_carrot(grid, start_row, start_col):
rows = len(grid)
cols = len(grid[0])
visited = [[False] * cols for _ in range(rows)]
visited[start_row][start_col] = True
queue = deque([(start_row, start_col, 0)])
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while queue:
r, c, d = queue.popleft()
if grid[r][c] == "C":
return d
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
continue
if visited[nr][nc] or grid[nr][nc] == "X":
continue
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.