시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB331192158725.291%

문제

세준 주차장은 R×C크기의 직사각형 모양이다. 세준 주차장에는 N개의 차와, M개의 주차 구역이 있다. 그리고, 모든 차는 주차 구역에 주차하려고 한다. 교통 제한 때문에, 차는 주차장의 경계와 평행하게만 움직일 수 있고, 모든 차는 1초에 한 칸씩 움직일 수 있다.

보통 모든 차는 현재 위치에서 가장 가까운 위치에 있는 주차 구역에 주차를 하려고 한다. 하지만, 다음과 같이 생긴 주차장이라면 현재 위치에서 가장 가까운 위치에 주차하는 것이 비효율적이다.

.C.....P.X...
XX.......X..P
XX.....C.....

‘C’는 차이고, 'P‘는 주차 구역, 'X'는 벽이고, '.'은 빈 공간이다.

만약 아래에 있는 차가 현재 위치에서 가장 가까운 곳에 주차를 한다면, 왼쪽 위에 있는 차는 가장 오른쪽에 있는 주차 구역에 주차를 해야 할 것이다. 이렇게 되면, 그 차가 주차하기 까지 14라는 시간이 걸린다. 하지만, 만약 아래에 있는 차가 오른 쪽에 있는 주차 구역에 주차를 하게 된다면, 두 차가 주차하기 까지 6이라는 시간이 걸린다.

현재 주차장의 모양과, 차의 위치, 주차 구역의 위치가 주어졌을 때, 모든 차가 주차하는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오. 차는 매우 작기 때문에, 한 칸에 여러 대의 차가 동시에 들어갈 수 있다. 차는 빈 공간과, 주차 구역만 통과할 수 있지만, 벽은 통과할 수 없다.

만약 모든 차가 주차하는 것이 불가능하다면, -1을 출력한다.

입력

첫째 줄에 주차장의 세로 크기 R과 가로 크기 C가 주어진다. R과 C의 크기는 50보다 작거나 같다. 둘째 줄부터 R개의 줄에는 주차장의 정보가 주어진다. 주차장의 정보는 문제에서 설명한 문자로 이루어져 있다. 차의 개수와, 주차 구역의 개수는 모두 0보다 크거나 같고 100을 넘지 않는다.

출력

첫째 줄에 모든 차가 주차하는데 걸리는 시간의 최솟값을 출력한다. 차가 없는 경우는 0을 출력한다.

예제 입력 1

3 7
C.....P
C.....P
C.....P

예제 출력 1

6

예제 입력 2

4 8
C.X.....
..X..X..
..X..X..
.....X.P

예제 출력 2

16

예제 입력 3

6 11
XXXXXXXXXXX
X......XPPX
XC...P.XPPX
X......X..X
X....C....X
XXXXXXXXXXX

예제 출력 3

5

예제 입력 4

5 3
.C.
...
C.C
X.X
PPP

예제 출력 4

4

예제 입력 5

3 5
CCCCC
.....
PXPXP

예제 출력 5

-1

예제 입력 6

3 5
..X..
C.X.P
..X..

예제 출력 6

-1

출처

  • 문제를 번역한 사람: baekjoon
  • 빠진 조건을 찾은 사람: HyehwA
  • 문제의 오타를 찾은 사람: mic1021