프리즌 브레이크
시간 제한2초메모리 제한128 MB
벽과 사람이 있는 빈 칸, 초당 한 명만 통과 가능한 출구가 있는 격자에서 모든 사람이 탈출하는 최소 시간을 구하거나 불가능함을 판별합니다.
문제
N×M 크기의 감옥이 있다. 각 칸은 벽(X), 빈 칸(.), 탈출구(D) 중 하나다. 모든 빈 칸에는 사람이 정확히 한 명씩 있다. 모든 사람은 탈출구 중 하나로 이동해 감옥 밖으로 나가야 한다.
사람이 상하좌우로 인접한 한 칸을 이동하는 데에는 1초가 걸린다. 하나의 탈출구에서는 매초 최대 한 명만 나갈 수 있다. 이동 중에는 같은 빈 칸에 여러 사람이 동시에 있어도 된다.
감옥 정보가 주어질 때, 모든 사람이 탈출하는 데 필요한 최소 시간을 구하시오. 감옥의 가장자리는 항상 벽 또는 탈출구이며, 내부에는 탈출구가 없다. 탈출구가 하나도 없을 수 있고, 빈 칸은 하나 이상 존재한다.
입력
첫째 줄에 감옥의 행 수와 열 수 N, M이 공백으로 구분되어 주어진다.
다음 N개의 줄에는 감옥의 정보가 주어진다. X는 벽, .은 빈 칸, D는 탈출구를 의미한다.
출력
모든 사람이 탈출하는 데 필요한 최소 시간을 첫째 줄에 출력한다. 모든 사람이 탈출할 수 없다면 impossible을 출력한다.
제한
- 3 <= N, M <= 12