트레일
면접 대비시간 제한1초메모리 제한1024 MB
땅, 숲, 물에 들어갈 때 각각 3일, 5일, 8일이 걸리는 격자에서 가장 왼쪽 열까지 가는 최단 시간을 구하고 기한과 비교합니다.
문제
Ann은 거친 변방의 운송 회사에서 일한다. 그녀의 일은 간단하다. 정해진 기한 안에 소포를 서쪽으로 배달해야 한다. 지도와 기한이 주어졌을 때, Ann이 목적지에 언제 도착하는지, 그리고 기한에 늦었는지 구하라.
지도는 Ann이 지나야 하는 지역을 위에서 내려다본 그림이다. 한 칸을 건너는 데 평지는 3일, 숲은 5일, 물은 8일이 걸린다. 바위를 넘으면 마차가 망가지므로 Ann은 바위를 건널 수 없다. 목표는 서쪽, 즉 지도의 가장 왼쪽 열에 도달하는 것이다. 이동은 북, 동, 남, 서 네 방향으로만 가능하며 대각선 이동은 없다. 지도에 따라서는 Ann이 서쪽에 도달할 수 없을 수도 있다.
가장 왼쪽 열에는 .만 있으며, 이 열을 건너는 시간은 계산에 포함하지 않는다.
입력
첫 줄에는 데이터 세트의 개수 n이 주어진다. 각 데이터 세트는 다음과 같다.
- 행의 수 rows와 열의 수 cols가 주어진다. 둘 다 1 이상 50 이하이다.
- 다음 rows줄에는 cols개의 문자로 지도가 주어진다. 각 문자는 다음 중 하나이다.
.: 평지W: 물R: 바위F: 숲S: Ann의 출발 위치. 한 번만 나타난다.
- 마지막 줄에는 기한까지 남은 날 수가 1 이상 300 이하의 정수로 주어진다.
출력
Ann이 기한 안에 서쪽에 도착하면 "The Package arrived with d day(s) to spare."를 출력한다. 여기서 d는 원래 기한까지 남은 날 수다. 기한 안에 배달할 수 없으면 "The Package was not delivered in time."을 출력한다.