You are given a 2D floor plan grid. Each cell is one of:
-
.
empty space (walkable)
-
#
wall/blocked (not walkable)
-
P
a person
-
E
an exit
A person can move 1 step per minute to the 4-neighbors (up/down/left/right) through walkable cells. Multiple people can occupy the same cell at the same time (ignore collisions).
Task:
-
Determine whether
every
person can reach
some
exit.
-
If everyone can escape, return the
minimum time until all people have escaped
, assuming each person walks optimally (i.e., the maximum over people of their shortest-path distance to any exit).
If some person cannot reach any exit, return -1.
Explain an algorithm and its time/space complexity.