← 返回 snapchat 的题目列表Grid Evacuation Reachability / Minimum Escape Time (Multi-source BFS)
类型：online_judge
Problem: Building Evacuation (Multi-source BFS)
You are given a building floor plan as an m x n grid:
.: empty cell (walkable)
#: obstacle (blocked)
E: exit (one or more)
P: person (one or more)
A person can move one step per time unit to one of the four directions (up/down/left/right). They cannot leave the grid or move through obstacles.
Tasks
Determine whether every person can reach any exit.
If everyone can reach an exit, return the maximum among all people’s shortest escape times (i.e., the minimum time needed to get everyone out).
If any person cannot escape, return -1.
Input (stdin)
The first line contains two integers m n. Then m lines follow, each a string of length n consisting of . # E P.
Output (stdout)
Print a single integer:
-1 if any person cannot reach an exit
otherwise the minimum time for all people to escape (max shortest path)
Constraints
1 <= m, n <= 200
counts of P and E are both >= 1
Test Cases
Case 1 Input:
3 4
P..E
.##.
P...
Output:
4
Case 2 Input:
2 3
P#E
###
Output:
-1
Case 3 Input:
3 3
E..
...
..P
Output:
4
Case 4 Input:
3 5
P...E
#####
E...P
Output:
-1
Case 5 Input:
1 6
P...EE
Output:
3
Example
Input
3 4
P..E
.##.
P...
Output
4