Fire Evacuation Plan

Time limit1sMemory limit128 MB

Summary

Given a grid with walls, flowers, people, and one exit, find the minimum time for everyone to reach the exit, where no two people may occupy the same cell at the same second.

Level: Hard8 of 10
Topics: BFS, Graph, Binary search, Dynamic programming
Solved: No attempts yet

Problem

On a sunny day, many people of Orangeland are visiting a flower garden that occupies a rectangular area. Suddenly a fire alarm throws everyone into chaos, and each person tries to reach the single exit door as quickly as possible while taking care not to trample the flowers (kept in fire-proof glass boxes) or collide with other people. Your task is to find the best evacuation plan for these well-mannered visitors.

The garden is modeled as a rectangular grid. Each cell either contains flowers or is a spot a person can stand on. Moving from one cell to one of its four edge-adjacent cells takes exactly one second. Such a move is allowed only if, at the next second, the destination cell holds no flowers and no other person. In particular, if two people could enter the same cell at the same second, the plan must admit only one of them; the other must wait, unless it has another cell to move to.

Compute the minimum number of seconds needed to evacuate the whole garden, that is, until everyone has reached the exit door. It is guaranteed that every person has at least one flower-free path from the starting cell to the exit door.

Input

The input contains several test cases. Each test case begins with a line holding two integers $n$ and $m$ ( $3 \le n, m \le 100$ ): the garden has $n$ rows and $m$ columns, and every cell is $1 \times 1$ . Each of the next $n$ lines contains $m$ characters, drawn from #, F, P, -, *, describing the garden at the moment the alarm sounds:

# marks the garden boundary.
* marks the exit door; there is exactly one, and it lies on the boundary in place of a #.
F marks a cell occupied by flowers.
P marks a cell occupied by a person.
- marks a free cell.

The input ends with a line containing 0 0, which is not part of any test case.

Output

For each test case, print a single line containing the minimum number of seconds required to evacuate the garden.

Examples3

Example 1

Input

3 3
###
#P#
#*#
4 5
#####
#PFP#
#P--*
#####
0 0

Expected output

1
4

Example 2
Input
```
4 4
####
#PP*
#PP#
####
0 0
```
Expected output
```
4
```
Example 3
Input
```
3 6
######
#P---*
######
0 0
```
Expected output
```
4
```