시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 176 83 63 56.757%

문제

재재새는 치즈를 너무 너무 좋아한다.

치즈를 너무 너무 좋아하지만, 재재새가 치즈를 먹는데는 1가지 원칙이 있다.

여기저기 치즈를 먹으면 어떤 치즈를 먹었는지 모르기 때문에, 번호를 매겨 1번, 2번, 3번, ... 치즈를 순서대로 먹어치운다.

재재새를 위해서, 이미 모든 치즈에는 번호가 매겨져 있으며, 치즈를 하나 먹을때 마다 재재새의 능력치가 1씩 증가한다.

사실, 재재새는 능력치와는 관계없이 어떤 치즈든 쉽게 먹어치울 수 있지만, 순서대로 먹기위해서, 능력치가 기준 이하면 치즈를 먹지 않고 지나간다. (치즈의 번호가 3이라면, 능력치가 3미만일때는 먹을 수 가 없다.) 또한, 재재새는 장애물(X)을 넘지 않으며, (상, 하, 좌, 우)로 한칸 씩 이동할때 마다, 1분씩 소요된다. 또한, 초기 재재새의 능력치는 1, 시작지점은 S이다. 단, 치즈를 먹는데는 시간이 소요되지 않는다.

입력

재재새가 돌아다닐 맵의 크기가 높이(H), 폭(W)순으로 주어지며, 각각 1000이하의 자연수다.

마찬가지로, 재재새가 먹어야하는 치즈의 수 N이 주어지며, N은 9 이하의 자연수다.

출력

재재새가 순서대로 모든 치즈를 먹고 끝내는데, 걸리는 최소 시간을 구해주면 된다.

예제 입력

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

예제 출력

4

예제 입력 2

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

예제 출력 2

12

예제 입력 3

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.......

예제 출력 3

91

힌트