Katkat
Back

Wildfire Grid: Days Until Quiet with Expiring Firebreaks

OpenAISoftware Engineer · Onsite
HardSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Simulate a wildfire spreading through a forest grid to find how many days until it stops spreading, then extend the model with fire-resistant trees and firebreaks that only hold for a limited number of days before the protected tree becomes flammable.

A forest is modeled as an R x C grid. Each cell is one of: empty ground, a healthy tree, or a tree already on fire. Fire spreads once per day: at the end of each day, every healthy tree that is 4-directionally adjacent to a tree that was already on fire at the end of the previous day catches fire too. Trees on fire at the very start count as burning on day 0. Empty cells never catch fire and never stop fire from reaching past them diagonally -- but since spread is only 4-directional, an empty cell does block a direct path through it.

This question is asked in progressively harder parts; your solution from each part should extend cleanly into the next rather than being thrown away.

Part 1 -- Days until the forest goes quiet

Starting from the grid as given, work out how many full days pass before nothing further ignites -- that is, the index of the final day where at least one more tree catches on fire, reporting 0 whenever the forest was already in a steady state from the first moment (including the case of a grid with no fire anywhere).

What this part should cover: correct handling of multiple separate fire sources burning simultaneously; a healthy tree that no fire can ever reach; the time and space complexity of your approach, in terms of the number of cells; and a brief comparison between literally simulating day by day versus a smarter traversal.

Part 2 -- Fire-resistant trees

Some cells now hold fire-resistant trees, which can never catch fire under any circumstances. Update your solution, and justify in your write-up whether a fire-resistant tree blocks the fire from reaching trees on its far side (it does not create a special barrier -- fire simply cannot pass through a cell that can never burn, same as it can't pass through empty ground, but it can still go around one).

Part 3 -- Firebreaks that expire

Some healthy trees are now additionally marked as temporarily protected by a firebreak that holds for a known number of days: a tree protected with value k cannot catch fire on days 0 through k - 1, no matter how long it has been adjacent to fire, but behaves like an ordinary healthy tree from day k onward (it can catch fire on day k itself if a fire-adjacent condition is already met by then). Extend your solution to compute the correct days-until-quiet value under this rule.

Example (Part 3)

Grid:  F H H     (row 0 only; F = burning, H = healthy)
Firebreak: cell (0,1) protected through day 2 (k = 3)

Day 0: (0,0) burning.
Day 1-2: (0,1) is adjacent to fire but still protected; nothing new catches.
Day 3: (0,1)'s protection has just expired and it is adjacent to fire -> catches fire.
Day 4: (0,2) is now adjacent to a tree that caught fire the day before -> catches fire.

days_until_quiet = 4

Constraints

  • 1 <= R, C <= 500
  • A firebreak value k is a non-negative integer no larger than R * C.
  • Assume at most a few dozen fire-resistant or protected cells relative to grid size is typical, but do not assume it.

Hints

Hint 1

For Part 1, think of every initially-burning cell as a source in a simultaneous multi-source breadth-first search, where the BFS layer number is exactly the day a cell caught fire -- this avoids re-scanning the whole grid once per simulated day.

Hint 2

For Part 2, trace through the spread rule for a single fire-resistant cell: does anything in your Part 1 code even reference it, other than the one check that decides whether a cell is allowed to be set on fire at all?

Hint 3

For Part 3, notice that an ordinary BFS layer number is no longer guaranteed to be the true ignition day once some cells have a built-in minimum day they're allowed to catch fire -- a cell reached 'early' by the wavefront still can't ignite before its protection expires.

Hint 4

A priority queue ordered by candidate ignition day, where you push a neighbor with day = max(current day + 1, that neighbor's protection expiry), turns Part 3 into something very close to Dijkstra's algorithm rather than plain BFS.

Follow-up questions

  • How would you report, for every tree, the exact day it caught fire (or that it never did), rather than just the overall last day?
  • What changes if fire can also spread diagonally, or if different trees burn at different speeds (a tree takes more than one day to finish igniting its neighbors)?
  • How would you handle a firebreak that can be reapplied -- say, a ranger re-treats a tree, resetting its protection countdown -- as an operation that happens mid-simulation?
  • Your current approach assumes the whole grid and all firebreaks are known up front. How would the design change if cells could turn into fire-resistant trees over time, in response to the fire's own progress?