시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
15 초 128 MB 83 10 4 13.793%

문제

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

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

JOI는 특산품가게가 있는 구획으로 들어가면, 일본에 있는 친구를 위해서 특산품을 살려고 한다.  JOI는 특산품 가게를 꼼꼼히 미리 조사해 두었으며, 특산품 가게에 가면 몇개의 특산품을 살수있는지 알고 있다. JOI가 최대 몇개의 특산품을 살수있는지에 대한 프로그램을 작성 하여라.

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

입력

입력은 1 + H 행으로 이루어져 있다.

1행은, 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'로 되어 있는 정수로 표시 되어있으며, 각 숫자는 특산품 가게에서 살수있는 최대의 개수를 나타낸다.

주어지는 입력값에서는 JOI가 처음에 있는 가장 북서쪽에 있는 구역은 길이라는 보장되어 있다. 또, JOI가 국제공항에 도착할수 있는것도 보장되어 있다.

출력

JOI가 살수있는 특산품의 개수의 최대값을 정수로 1행에 표시하여라.

예제 입력

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

예제 출력

11

예제 입력 2

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

예제 출력 2

27

힌트

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

출처

Olympiad > 일본정보올림피아드 예선 > JOI 2013 예선 6번