화재 대피 계획

시간 제한1초메모리 제한128 MB

요약

벽, 꽃, 사람, 출구가 있는 격자에서 모든 사람이 같은 초에 같은 칸에 있을 수 없다는 조건 아래 전원이 출구에 도착하는 최소 시간을 구한다.

난이도: 어려움10점 중 8점
유형: BFS, 그래프, 이분 탐색, 동적 계획법
정답자: 아직 제출이 없습니다

문제

맑은 날, 오렌지랜드의 많은 사람들이 직사각형 모양의 꽃 정원을 구경하고 있다. 갑자기 화재 경보가 울리자 모두가 혼란에 빠지고, 각자 하나뿐인 출구로 최대한 빨리 대피하려 한다. 이때 사람들은 (방화 유리 상자에 담긴) 꽃을 밟거나 다른 사람과 부딪히지 않도록 조심한다. 이 예의 바른 방문객들을 위한 최적의 대피 계획을 구하라.

정원은 직사각형 격자로 표현된다. 각 칸에는 꽃이 있거나, 사람이 서 있을 수 있는 빈 공간이 있다. 한 칸에서 상하좌우로 인접한 칸으로 이동하는 데 정확히 1초가 걸린다. 이 이동은 다음 순간에 도착 칸에 꽃이 없고 다른 사람도 없을 때에만 가능하다. 특히 두 사람이 같은 칸에 동시에 들어가려 한다면, 계획은 그중 한 명만 들어가게 해야 하며 나머지 한 명은 (이동할 다른 칸이 없는 한) 기다려야 한다.

정원 전체를 대피시키는 데, 즉 모든 사람이 출구에 도달할 때까지 필요한 최소 시간(초)을 구하라. 모든 사람은 시작 칸에서 출구까지 꽃을 피해 갈 수 있는 경로가 적어도 하나 존재함이 보장된다.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 두 정수 $n$ 과 $m$ ( $3 \le n, m \le 100$ )이 주어진다. 정원은 $n$ 개의 행과 $m$ 개의 열로 이루어지며, 각 칸의 크기는 $1 \times 1$ 이다. 이어지는 $n$ 개의 줄에는 각각 $m$ 개의 문자가 주어지며, 화재 경보가 울린 순간의 정원 상태를 나타낸다. 각 문자는 #, F, P, -, * 중 하나이다.

# : 정원의 경계
* : 출구. 정확히 하나 존재하며, 경계 위의 # 자리에 놓인다.
F : 꽃이 있는 칸
P : 사람이 있는 칸
- : 빈 칸

입력의 끝은 0 0으로 이루어진 줄로 표시되며, 이 줄은 어떤 테스트 케이스에도 포함되지 않는다.

출력

각 테스트 케이스마다 정원을 대피시키는 데 필요한 최소 시간(초)을 한 줄에 하나씩 출력한다.

예제3

예제 1

입력

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

예상 출력

1
4

예제 2
입력
```
4 4
####
#PP*
#PP#
####
0 0
```
예상 출력
```
4
```
예제 3
입력
```
3 6
######
#P---*
######
0 0
```
예상 출력
```
4
```