시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 1024 MB313806328.125%

문제

당신은 엄청난 불행 체질을 갖고 태어났다. 다행히 당신에게는 불행 체질을 받아내 주는 여자친구 한별이가 있다. 한별이는 운동신경이 매우 뛰어나 당신에게 닥치는 불상사들을 막아내주곤 한다. 하지만 그런 한별이에게도 한계가 있기에, 연속해서 너무 많은 불상사들이 생기는 경우에는 당신을 온전하게 지켜주지 못하게 된다.

현재 당신과 한별이는 학교에서 집으로 귀가하고 있다. 마을은 $N\times M$ 형태의 격자 모양이며, 당신과 한별이는 격자에서 상하좌우로 인접한 칸으로만 이동할 수 있다. 단, 일부 칸에는 벽이 있어 이동할 수 없다. 또, 당신은 한별이에게 길치처럼 보이고 싶지 않기 때문에, 바로 직전에 방문한 칸으로 돌아가는 행동은 하지 않는다.

오늘은 한별이가 당신의 집으로 놀러 가기로 한 날이기 때문에, 집으로 최대한 빨리 가려고 한다. 당신은 십수 년간의 경험을 바탕으로 마을의 각 좌표마다 일어나는 불상사의 개수를 미리 알아차릴 수 있다. 만약 가장 최근 지나온 $3$ 개 이하 칸에 있는 불상사의 개수 합이 $K$ 개를 넘으면, 한별이도 당신을 지켜주지 못해 부상을 입게 된다. 또, 당신의 불행 체질은 정말 엄청나기 때문에, 방문한 칸에 다시 방문하더라도 매번 같은 개수의 불상사가 다시 일어나게 된다. 과연 당신은 부상을 입지 않고 안전하게 귀가할 수 있을까?

입력

첫 번째 줄에 마을의 세로 크기 $N$, 가로 크기 $M$, 한별이가 연속해서 막을 수 있는 불상사의 개수 $K$가 주어진다. ($2\leq N,M\leq 1\,000$, $0\leq K\leq 27$)

다음 $N$ 개의 줄에 걸쳐 마을의 상태가 주어진다. 각 줄은 길이 $M$의 문자열로 주어진다. S는 학교, H는 집을 의미하고, X는 이동할 수 없는 벽을 의미한다. 이외의 칸에는 각 좌표에서 일어나는 불상사의 개수가 0부터 9까지의 숫자로 주어진다. 학교와 집은 각각 한 개씩만 존재하며, 학교와 집에서는 불상사가 일어나지 않는다.

출력

학교에서 집으로 안전하게 이동할 수 있을 때, 가능한 경로 중 최단 거리를 출력하시오. 만약 안전하게 귀가하지 못한다면 -1을 출력한다.

예제 입력 1

6 6 4
S1113X
33323X
11211X
13311X
1XXXXX
11111H

예제 출력 1

20

예제 입력 2

3 5 4
12121
1X1X1
SX1XH

예제 출력 2

-1

출처

Contest > BOJ User Contest > 아니메컵 > 아니메컵 2쿨 I번