Multi-source BFS + heap
Plan a Quiet Delivery
01. The question
A delivery robot crosses a square floor from top-left to bottom-right. Cells marked 1 contain noisy machines. Maximize the smallest Manhattan distance to any machine along the walk. Return both the clearance and an actual route.
| r / c | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 1 | 0 | 0 | 0 |
1 is a noisy machine, not a wall. Choose a route from [0,0] to [3,3] with the greatest worst clearance.
Before revealing the idea, predict the result and describe what information you would need to track.
02. Worked example
Input4 × 4 floor; machines at (0, 3) and (3, 0)
Output{"clearance": 2, "route": [[0,0], [0,1], [1,1], [1,2], [2,2], [2,3], [3,3]]} (one optimal route)
- BFS from both machines gives each cell its distance to the closest noise source.
- A route through the middle can keep clearance 2 throughout the walk.
- Clearance 3 is impossible: both neighbors of the start have distance 2.
- Return clearance 2 and the cells of one route achieving it, not just the score.
Try your code
Define solve(data, parameter="") and return your result. Your code runs locally, not on a server.
Edit your test cases
Use 1-10 objects with data and an optional string parameter. Expected outputs are computed from the lesson. An optional expected field must be correct.
Input contract & reference code
Example data: [[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]]. Parameter: "". Numeric parameters arrive as strings; convert them with int(parameter) when needed.
The example and generated cases use the question’s exact variant. This checks behavior on a small test batch—not performance on every possible input.
Python downloads only when you run code, using compressed runtime assets. Code is not saved or uploaded. Enable JavaScript to run it.
Printed output
Five-second execution limit per batch. Standard-library Python only; additional packages and network access are unavailable. Stop ends execution without blocking the lesson.
03. The idea
Try sketching your own approach first. What would you track, and why would it work?
Reveal the idea
- Run BFS from all machines to measure nearest-source distances.
- Use a max-priority search to choose the highest-clearance pending route.
- Keep the route with each candidate. Extend with min(current clearance, next distance), and return both pieces at the goal.
04. Watch it happen
Use Step to move slowly, or Play to follow the whole trace. Change a preset or load your own input.
Input & settings
Red = current item / blue = active window or cells / green = completed work. A value docks at its actual destination; the original input stays unchanged. Positions start at 0.
Working state / what changes
Ready to begin
Enable JavaScript to step through the animation. The worked example and solution below remain readable without it.
Python / why it changes
The line behind the step
from collections import deque
from itertools import count
import heapq
def quiet_delivery(grid):
n = len(grid)
distance = [[-1] * n for _ in range(n)]
queue = deque()
for row in range(n):
for col in range(n):
if grid[row][col] == 1:
distance[row][col] = 0
queue.append((row, col))
directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
while queue:
row, col = queue.popleft()
for dr, dc in directions:
nr, nc = row + dr, col + dc
if 0 <= nr < n and 0 <= nc < n and distance[nr][nc] == -1:
distance[nr][nc] = distance[row][col] + 1
queue.append((nr, nc))
order = count()
heap = [(-distance[0][0], 0, 0, next(order), [[0, 0]])]
visited = set()
while heap:
negative_safe, row, col, _, route = heapq.heappop(heap)
if (row, col) in visited:
continue
visited.add((row, col))
safe = -negative_safe
if (row, col) == (n - 1, n - 1):
return {"clearance": safe, "route": route}
for dr, dc in directions:
nr, nc = row + dr, col + dc
if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in visited:
next_safe = min(safe, distance[nr][nc])
next_route = route + [[nr, nc]]
heapq.heappush(heap, (-next_safe, nr, nc, next(order), next_route))How to use this walkthrough
Hover or focus a control for its label. Play forms the input and follows values into the working state. Step shows one change; Back and the slider restore exact snapshots. Reduced motion uses instant updates. Saved snapshots and sorted heap displays are teaching overhead, not algorithm complexity.
05. Python solution
from collections import deque
from itertools import count
import heapq
def quiet_delivery(grid):
n = len(grid)
distance = [[-1] * n for _ in range(n)]
queue = deque()
for row in range(n):
for col in range(n):
if grid[row][col] == 1:
distance[row][col] = 0
queue.append((row, col))
directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
while queue:
row, col = queue.popleft()
for dr, dc in directions:
nr, nc = row + dr, col + dc
if 0 <= nr < n and 0 <= nc < n and distance[nr][nc] == -1:
distance[nr][nc] = distance[row][col] + 1
queue.append((nr, nc))
order = count()
heap = [(-distance[0][0], 0, 0, next(order), [[0, 0]])]
visited = set()
while heap:
negative_safe, row, col, _, route = heapq.heappop(heap)
if (row, col) in visited:
continue
visited.add((row, col))
safe = -negative_safe
if (row, col) == (n - 1, n - 1):
return {"clearance": safe, "route": route}
for dr, dc in directions:
nr, nc = row + dr, col + dc
if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in visited:
next_safe = min(safe, distance[nr][nc])
next_route = route + [[nr, nc]]
heapq.heappush(heap, (-next_safe, nr, nc, next(order), next_route))06. Cost & edge cases
- Time
- O(n⁴) worst case including path copies; O(n² log n) for the score-only search
- Space
- O(n⁴) worst case when storing full routes for pending candidates
- At least one machine is required. Coordinates are zero-based (row, column).
- A machine at the start or destination forces clearance 0.
- Machines are not walls in this simplified model. Full routes are copied for clarity; a production implementation can use predecessor pointers instead.