joi 2010/2011 예선 5- 제리의 치즈먹기 (Cheese) > 문제은행 : 정보올림피아드&알고리즘




2893 : 제리의 치즈먹기 (Cheese)

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
134 회   
시도횟수
453 회   

문제

올해도 톰이 운영하는 치즈 공장이 치즈 생산을 시작하자, 생쥐 제리가 둥지에서 얼굴을 내밀었다. 톰과 제리가 사는 ‘치즈피아’ 시는 동서남북으로 구획 정리되어 있고, 각 구획은 제리의 둥지, 치즈 공장, 장애물 공터 중 하나이다. 제리는 둥지에서 출발하여 모든 치즈 공장을 방문하여 치즈를 1 개씩 먹는다.

 

‘치즈피아’ 시에는 N 개의 치즈 공장이 있고, 어떤 공장도 1 종류의 치즈만을 생산하고있다. 치즈의 딱딱한 정도는 공장에 따라 다르고 딱딱한 정도 1에서 N까지의 치즈를 생산하는 치즈 공장이 각각 하나씩만 있다.

 

제리의 첫 번째 체력은 1 이며, 치즈를 1 개 먹을 때마다 체력이 1 증가한다. 그러나 제리는 자신의 체력보다 딱딱한 치즈를 먹을 수 없다.

 

생쥐 제리는 동서남북에 인접한 부지로 이동하는데 1분이 걸린다. 하지만 인접한 부지가 장애물인 경우 인접한 부지에 들어갈 수 없다. 인접한 부지가 치즈 공장인 경우에는 그 공장의 치즈를 먹지 않고 지나갈 수도 있다. 모든 치즈를 먹고 끝내는 데 걸리는 최소 시간을 구하는 프로그램을 작성하라. 생쥐 제리가 치즈를 먹는 데 걸리는 시간은 무시할 수 있을 만큼 짧다. 


입력형식

입력은 H + 1 행으로 이루어진다. 첫 번째 행에는 세 개의 정수 H, W, N (1 <= H, W <= 1000, 1 <= N <= 9)이 공백으로 구분하여 주어진다. 두 번째 줄에서 H + 1 번째 줄까지의 각 행에는 'S', '1', '2', ..., '9', 'X', '.'로 이루어진 W개의 문자열이 주어지며, 각각의 문자는 각 영역의 상태를 나타낸다. 제리의 둥지인 경우 'S'이고, 장애물 인 경우 'X', 공터이면 '.'가 되고, 치즈를 생산하는 공장인 경우는 각각 '1', '2', ..., '9'가된다. 각 숫자는 딱딱한 정도를 나타낸다. 입력 데이터에는 제리의 둥지 ‘S’와 치즈를 생산하는 공장 1, 2, ..., N 이 각각 하나씩 있다. 쥐는 모든 치즈를 먹을 수 있는 것이 보증되어 있다.

출력형식

제리가 모든 치즈를 체력에 맞추어 먹고 끝내는 데 걸리는 최소 시간 (분)을 나타내는 정수를 한 줄로 출력하라.

입력 예

3 3 1
S..
...
..1

출력 예

4

입력 예

4 5 2
.X..1
....X
.XX.S
.2.X.

출력 예

12

입력 예

10 10 9
.X...X.S.X
6..5X..X1X
...XXXX..X
X..9X...X.
8.X2X..X3X
...XX.X4..
XX....7X..
X..X..XX..
X...X.XX..
..X.......

출력 예

91


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP