프리즌 브레이크

N×M 크기의 감옥이 있다. 각 칸은 벽(X), 빈 칸(.), 탈출구(D) 중 하나다. 모든 빈 칸에는 사람이 정확히 한 명씩 있다. 모든 사람은 탈출구 중 하나로 이동해 감옥 밖으로 나가야 한다.

사람이 상하좌우로 인접한 한 칸을 이동하는 데에는 1초가 걸린다. 하나의 탈출구에서는 매초 최대 한 명만 나갈 수 있다. 이동 중에는 같은 빈 칸에 여러 사람이 동시에 있어도 된다.

감옥 정보가 주어질 때, 모든 사람이 탈출하는 데 필요한 최소 시간을 구하시오. 감옥의 가장자리는 항상 벽 또는 탈출구이며, 내부에는 탈출구가 없다. 탈출구가 하나도 없을 수 있고, 빈 칸은 하나 이상 존재한다.

첫째 줄에 감옥의 행 수와 열 수 N, M이 공백으로 구분되어 주어진다.

다음 N개의 줄에는 감옥의 정보가 주어진다. X는 벽, .은 빈 칸, D는 탈출구를 의미한다.

모든 사람이 탈출하는 데 필요한 최소 시간을 첫째 줄에 출력한다. 모든 사람이 탈출할 수 없다면 impossible을 출력한다.

• 3 <= N, M <= 12