cho.sh우아한 전시장
격자 위의 자동차가 가장자리 문까지 가야 하고, 지나가는 칸의 자동차는 모두 치워야 한다. 옮기는 자동차 수를 최소로 하는 경로를 찾는다.
보통6그래프최단 경로힙BFS면접 대비아직 제출이 없습니다시간 제한2초메모리 제한512 MB문제
자동차 전시장은 실내에 자동차를 빽빽하게 세워 두는 공간이다. 한 대를 밖으로 빼내려면 그 앞을 막고 있는 자동차부터 다른 곳으로 옮겨야 한다.
전시장은 R×C 격자로 주어진다. 각 칸은 벽, 자동차, 문, 빈 바닥 중 하나이다. 자동차는 상하좌우로 인접한 빈 칸으로만 움직이고 대각선으로는 움직이지 못한다. 제자리에서 방향을 바꿀 수 있으므로 자동차가 향한 방향은 생각하지 않는다. 문은 자동차가 지나갈 만큼 넓어서, 자동차는 문이 있는 칸을 그대로 지나갈 수 있다.
격자의 첫 행, 마지막 행, 첫 열, 마지막 열은 모두 벽 또는 문이다. 이 테두리에 있는 문을 지나면 자동차는 건물 밖으로 나간다.
빼내려는 자동차 한 대의 위치가 주어진다. 이 자동차가 지나갈 경로를 하나 정하면, 그 경로 위에 놓인 자동차는 모두 미리 다른 곳으로 옮겨야 한다. 옮기는 자동차의 수는 경로 위에 있는 자동차의 수에 빼내려는 자동차 자신을 더한 값이다. 이 값의 최솟값을 구하라.
입력
첫째 줄에 전시장의 행 수와 열 수를 나타내는 두 정수 R, C가 주어진다. (3≤R,C≤400)
다음 R개 줄에는 각각 길이가 C인 문자열이 주어진다. 각 문자의 뜻은 다음과 같다.
#: 벽c: 자동차D: 문.: 빈 바닥
첫 행과 마지막 행의 모든 문자, 그리고 각 행의 첫 문자와 마지막 문자는 # 또는 D이다.
마지막 줄에 빼내려는 자동차의 위치를 나타내는 두 정수 r, c가 주어진다. (1<r<R, 1<c<C) 왼쪽 위 칸의 좌표가 1 1이고, r은 행 번호, c는 열 번호이다. r행 c열에는 자동차가 있다.
이 자동차가 건물 밖으로 나가는 경로가 적어도 하나 존재한다.
출력
첫째 줄에 빼내려는 자동차가 건물 밖으로 나가기까지 옮기는 자동차 수의 최솟값을 출력한다. 빼내려는 자동차 자신도 센다.