배달
면접 대비시간 제한2초메모리 제한128 MB
격자에서 같은 방향으로 두 번 연속 이동할 수 없는 제약 아래 두 목표 지점을 모두 방문하는 최소 이동 시간을 구합니다.
문제
민식이는 포장을 마친 선물을 교실 안의 두 장소에 배달하려고 한다. 교실은 세로 N칸, 가로 M칸의 직사각형 격자로 이루어져 있으며, 각 칸은 같은 크기의 정사각형이다.
지도에는 다음 문자가 주어진다.
S: 민식이가 처음 서 있는 칸이다. 정확히 한 칸만 있다.C: 선물을 배달해야 하는 칸이다. 정확히 두 칸이 있다.#: 지나갈 수 없는 칸이다..: 자유롭게 지나갈 수 있는 칸이다.
민식이는 1분에 상하좌우로 인접한 한 칸을 이동할 수 있고, 교실 밖으로 나갈 수 없다. C 칸에 들어가면 그 칸에서 해야 할 배달은 즉시 완료되며 추가 시간은 걸리지 않는다.
민식이는 매 분마다 이전과 다른 방향으로 이동해야 한다. 따라서 같은 방향으로 두 번 연속 이동할 수 없다. 두 C 칸을 모두 방문하는 데 필요한 최소 시간을 구하시오.
입력
첫째 줄에 교실의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50 이하의 자연수이다.
둘째 줄부터 N개의 줄에 교실의 지도가 주어진다.
출력
두 배달 장소를 모두 방문하는 데 걸리는 최소 시간을 출력한다. 불가능하면 -1을 출력한다.