dave winer is stuck on a deserted island, with lots of trees, which is very thin and ten miles long (east to west). large cliffs surround the entire island and if he jumped off, he wouldn’t survive the fall. a fire starts burning at the west side of the island. unfortunately this island always has a west to east blowing wind blowing at 2mph and this moves the fire slowly toward dave at 1mph. (so he only has ten hours left). save dave (or maybe, let him burn :-) ! what to do?
Solution
someone suggested he could dig a pit across the island to act as a firebreak. good suggestion, if he had a shovel and the ground wasn’t too hard.
but even if he didn’t have a shovel, he could pick up a branch and run up to the fire and light the branch. then run all the way to the eastern edge of the island, but stop about a mile short. there he could light all those trees on fire and they would start burning and the fire would move east. it would consume all that vegetation in an hour, and then dave could wait for awhile for that part to cool down some. when the initial fire reached him, he could just run into the already burnt part, and the fire couldn’t get him.
T = tree
D = dave
B = burnt
top view
==========================
| fire-> T T T T T T T D |
==========================
dave gets branch and lights it from fire
==========================
| fire-> D T T T T T T T |
==========================
dave lights trees farther east on the island
==========================
| fire-> T T T T D fire->|
==========================
dave waits until second fire cools, and then hides out there
==========================
| B B B fire-> T T B B D |
==========================
dave is saved!
2026 Update: Shortest Path in a Burning Graph — BFS with Two Sources
The “Dave’s on Fire” type puzzle maps to a classic graph problem: given a grid where fire spreads and a person must escape, find if escape is possible and the minimum time. This is a multi-source BFS problem.
from collections import deque
def escape_from_fire(grid: list) -> int:
"""
Grid contains: '.' (empty), '#' (wall), 'D' (Dave), 'F' (fire), 'E' (exit).
Fire spreads 1 cell per minute in 4 directions.
Returns min time for Dave to reach exit, or -1 if impossible.
LeetCode #2258 (Escape the Spreading Fire) variant.
"""
ROWS, COLS = len(grid), len(grid[0])
INF = float('inf')
# Find positions
dave_pos = fire_positions = exit_pos = None
fires = []
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == 'D':
dave_pos = (r, c)
elif grid[r][c] == 'F':
fires.append((r, c))
elif grid[r][c] == 'E':
exit_pos = (r, c)
def bfs_times(starts):
"""BFS from multiple start points. Returns time grid."""
times = [[INF] * COLS for _ in range(ROWS)]
q = deque()
for r, c in starts:
times[r][c] = 0
q.append((r, c))
while q:
r, c = q.popleft()
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r+dr, c+dc
if 0 <= nr < ROWS and 0 <= nc < COLS and grid[nr][nc] != '#' and times[nr][nc] == INF:
times[nr][nc] = times[r][c] + 1
q.append((nr, nc))
return times
fire_times = bfs_times(fires)
dave_times = bfs_times([dave_pos])
er, ec = exit_pos
dave_exit_time = dave_times[er][ec]
fire_exit_time = fire_times[er][ec]
if dave_exit_time == INF:
return -1 # Dave can't reach exit
if dave_exit_time < fire_exit_time:
return dave_exit_time # Dave arrives before fire
# Binary search: can Dave delay start by k minutes and still escape?
# (for more complex variants)
return -1
# Example grid
grid = [
['.', '.', '.', 'E'],
['.', '#', '#', '.'],
['D', '.', 'F', '.'],
['.', '.', '.', '.'],
]
print(escape_from_fire(grid))
Key BFS insight: Run BFS simultaneously from all fire sources (multi-source BFS) to get the earliest time fire reaches each cell. Then run BFS from Dave’s start. A cell is “safe” for Dave at time t if dave_time[cell] + t < fire_time[cell]. This converts the “spreading danger” problem into two separate BFS runs — O(ROWS × COLS) instead of O(ROWS × COLS × T).
Related LeetCode problems: #994 (Rotting Oranges), #1293 (Shortest Path with Obstacle Elimination), #2258 (Escape the Spreading Fire).