Escape Grid with Fire and Waiting Time

Given a grid with a start, target, blockers, and sometimes fire sources, decide whether escape is possible or compute the maximum safe waiting time before moving. Requirements Implement a grid escape solver. The prompt appears in two related forms: A floor plan has people, exits, and blockers; compute whether everyone can escape or the shortest escape time. A start and target are given; blockers may be added; then fire sources are introduced and you must find the maximum time you can wait at the start before leaving. For the fire variant, use a grid with: 0 = open cell 1 = fire source 2 = wall / blocker start = top-left or specified cell target = bottom-right or specified exit You should: Treat movement as 4-directional. Use multi-source BFS for fire arrival times. Use BFS for person movement under the rule that you cannot enter a cell after fire reaches it. Binary-search the waiting time if asked for the maximum safe delay. Clarify whether reaching the target at the same minute as fire is allowed. Notes The robust approach precomputes fire_time[r][c] by seeding a queue with all fire cells. Then can(wait) runs BFS from the start at time wait and only enters a cell if the person arrives before the fire. Many formulations allow arriving at the safehouse at the same time as fire; other cells usually require strict earlier arrival. For the simpler escape-time variant, a single-source or multi-source BFS from exits can compute nearest exit distance. If blockers are added dynamically, clarify whether you need to recompute from scratch or update incrementally; in a live coding round, recomputation is usually acceptable unless the interviewer gives many updates. Complexity is O(m * n * log(mn)) with binary search over wait time and BFS checks, or O(m * n) for a single reachability / shortest-time query. Preparation Implement LC 2258-style fire escape once from memory. Prepare a helper can(wait) and test the equality-at-safehouse rule. Drill edge cases: start blocked, target blocked, fire already at start, no fire, and no possible path.