Each cell of a grid charges a toll (a non-negative integer) to enter it. Starting on the top-left cell and moving up/down/left/right, return the minimum total toll to reach the bottom-right cell. The toll of every cell you stand on counts, including the start and the end.
lowestToll(grid)
Input format: rows separated by ;, values space-separated.
[[1,3],[2,1]] // → 4 (1 → 2 → 1)
[[1,2,3],[4,5,6]] // → 12 (1→2→3→6) or (1→4→5→6)... min is 1+2+3+6=12
[[5]] // → 5
Strip the grid dressing: every cell is a node, moving between adjacent cells is an edge costing the entered cell's toll. You want the cheapest total to get from top-left to bottom-right. Since tolls vary, fewest-moves (BFS) isn't enough — you need cheapest accumulated cost, which is Dijkstra's territory.
With four-directional movement, the grid has exponentially many corner-to-corner paths — brute force is out. The standard shortest-path insight: track the best toll found so far for every cell, and greedily commit to the cheapest unresolved cell each step, since non-negative tolls mean no future discovery through a currently-pricier cell could beat the one you're about to commit to.
Always stepping right or down seems natural, but a locally cheap cell can lead into an expensive patch, while a detour — even backward or sideways — might route around a costly region for less total cost. A wall of high-toll cells makes this concrete: the cheapest route might dodge an expensive column entirely by going down first, which a strict right/down-only walk would miss. Dijkstra doesn't commit to a direction — it always expands from whichever reachable cell currently has the lowest total cost, guaranteeing the true minimum.
def lowest_toll(grid):
rows = len(grid)
cols = len(grid[0])
dist = [[float("inf")] * cols for _ in range(rows)]
visited = [[False] * cols for _ in range(rows)]
dist[0][0] = grid[0][0]
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while True:
br, bc, best = -1, -1, float("inf")
for r in range(rows):
for c in range(cols):
if not visited[r][c] and dist[r][c] < best:
best = dist[r][c]
br, bc = r, c
if br == -1:
break
visited[br][bc] = True
for dr, dc in dirs:
nr, nc = br + dr, bc + dc
if 0 <= nr < rows and 0 <= nc < cols:
nd = dist[br][bc] + grid[nr][nc]
if nd < dist[nr][nc]:
dist[nr][nc] = nd
return dist[rows - 1][cols - 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.