6252번 - Fire Evacuation Plan 다국어채점 준비 중

In a sunny day, many people of the Orangeland are visiting a flower garden located in an amazing rectangular area in the country. Suddenly, the fire alarm puts all into chaos. Everyone tries to save his/her life by reaching the exit door. Unfortunately, the garden has only one exit door. While all try to reach the exit door as soon as possible, they care about not to trample the flowers (maintained in fire-proof glass boxes) and other people. You are responsible to write a program that finds the best fire evacuation plan for these well-civilized people.

You may assume the garden is modeled as a rectangular grid. In each cell, there exist either some flowers or a spot that one can stand on it. It takes one second for everybody to step from one cell to one of its four edge-adjacent cells. This movement can be done if the adjacent cell is not occupied by others in the next second and of course it is not occupied by flowers. Note that if two persons can simultaneously enter a cell, your fire evacuation plan must admit only one of them to enter the cell; the other one should wait unless he has other options to move. Your program must compute the minimum time needed to evacuate the garden, i.e. everyone reaches the exit door. You are guaranteed that for each person there exists a path from his/her initial cell to the exit door avoiding flowers.

There are multiple test cases in the input. Each test case starts with a line containing two integers n and m (3 ≤ n, m ≤ 100) that specify the length of the horizontal and vertical sides of the garden, respectively (each cell is 1×1). The next n lines, each contains m characters from the set {#, F, P, -,*}, representing the garden at the fire-alarm time. The boundary of the garden are denoted by “#” characters, except the exit door which is denoted by “*”. F and P indicate that the corresponding cell is respectively occupied by flowers or a person at the fire-alarm time. The free cells at the fire-alarm time are represented by “-“. The input terminates with a line containing “0 0”.

For each test case, display a single line containing the minimum time needed to evacuate the garden.