JOI 2012/2013 예선 6- 기념품 구매 계획 (Gifts) > 문제은행 : 정보올림피아드&알고리즘




2950 : 기념품 구매 계획 (Gifts)

제한시간
15000 ms   
메모리제한
128 MB   
해결횟수
10 회   
시도횟수
117 회   

문제

호주로 여행을 간 태영이는 다양한 장소에서 관광을 즐기고, 마침내 귀국하는 날이 왔다. 현재, 태영이는 돌아가는 비행기가 출발하는 국제공항의 동네에 있다. 그 마을에는 동서남북으로 구역정리가 되어있으며, 각 구역에는 길, 기념품, 주택, 국제공항이 있다. 태영이는 가장 북서쪽의 구역에서 출발하여 가장 남동쪽에 있는 구역의 국제공항으로 가려고 한다.

 

태영이는 지금부터 가장 가까운 구역을 이동할 수 있으며, 주택구역은 들어가지 못한다. 또 비행기출발 시간을 맞추기 위해서 지금 있는 구역부터 동쪽과 남쪽으로 밖에 이동 하지 못한다. 단, 시간이 어느 정도 여유가 있기 때문에, K번 동안 지금 있는 구역에서 북, 서쪽으로 이동이 가능하다.

 

태영이는 기념품 가게가 있는 구역으로 들어가면, 한국에 있는 친구 관영이를 위해서 기념품을 사려고 한다.  태영이는 기념품 가게를 꼼꼼히 미리 조사해 두었으며, 기념품 가게에 가면 몇 개의 기념품을 살 수 있는지 알고 있다. 태영이가 최대 몇 개의 기념품을 살 수 있는지에 대한 프로그램을 작성 하여라.

 

하지만, 기념품을 구매하는 시간은 무시하여도 좋으며, 같은 기념품을 2번 이상 찾았을 때는 처음 것만 계산한다.

 

입력 예 1을 보면
예제 1번에서, 먼저 태영이가 3번 남쪽으로 이동하여 구역(4,1)의 기념품가게에서 물건을 구매한 뒤에, 남쪽으로 1번, 동쪽으로 3번 더 가서, 거기서 북쪽으로 2번 뒤에 있는 구역(3,4)의 기념품 가게에서 물건을 구매하였다. 마지막으로 남쪽으로 2번 가서 국제공항에 도착하면 총 11개의 기념품을 구매할 수 있다.

 


입력형식

입력은 1 + H 행으로 이루어져 있다. 첫 행은, 3개의 정수 H, W, K(2 <= H <= 50, 2 <= W <= 50, 1 <= K <= 3)을 쓴다. H행은 W번의 횟수만큼 문자를 받고(W크기 만큼의 문자열), 각 문자는 구역의 정보를 가지고 있다. 북쪽에서 i번, 서쪽에서 j번의 구역을 (i,j)로 나타낸다. (1 <= i <= H, 1 <= j <= W) i행의 j번째는 문자는, 구역(i,j)가 '.'이면 국제공항으로 가는 길이고, '#'은 주택이 있는 장소 이며, 기념품가게가 있는 장소는 '1','2'....'9'로 되어 있는 정수로 표시 되어있으며, 각 숫자는 기념품 가게에서 살 수 있는 최대의 개수를 나타낸다. 주어지는 입력 값에서는 태영이가 처음에 있는 가장 북서쪽에 있는 구역은 길이라는 것이 보장된다. 또한, 태영이가 국제공항에 도착 할 수 있는 것도 보장된다.

출력형식

태영이가 살 수 있는 기념품의 개수의 최대값을 정수로 1행에 표시하여라.

입력 예

5 4 2
...#
.#.#
.#73
8##.
....

출력 예

11

입력 예

4 4 3
.8#9
9.#.
.#9.
....

출력 예

27


경기도 안양시 동안구 평촌대로 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