문제
올해도 JOI 마을의 치즈 공장이 치즈를 만들기 시작하자, 쥐가 굴에서 얼굴을 내밀었다. JOI 마을은 동서남북으로 구획이 나뉘어 있고, 각 칸은 굴, 치즈 공장, 장애물, 빈터 중 하나이다. 쥐는 굴에서 출발해 모든 치즈 공장에 들러 치즈를 하나씩 먹는다. 이 마을에는 치즈 공장이 \(N\)개 있고, 각 공장은 한 종류의 치즈만 만든다. 치즈의 단단함은 공장마다 다르며, 단단함 \(1\)부터 \(N\)까지의 치즈를 만드는 공장이 하나씩 있다. 쥐의 처음 체력은 \(1\)이고, 치즈를 하나 먹을 때마다 체력이 \(1\) 늘어난다. 다만 자신의 체력보다 단단한 치즈는 먹을 수 없다. 쥐는 동서남북으로 이웃한 칸으로 \(1\)분에 이동할 수 있지만, 장애물 칸에는 들어갈 수 없다. 치즈를 먹지 않고 공장을 지나칠 수도 있다. 모든 치즈를 다 먹기까지 걸리는 가장 짧은 시간을 구하는 프로그램을 작성하라. 치즈를 먹는 데 걸리는 시간은 무시한다. |
입력
입력은 다음 형식으로 주어진다.
\(H\) \(W\) \(N\)
\(S_1\)
\(S_2\)
\(\vdots\)
\(S_H\)
- 입력은 \(H+1\)줄이다.
- 첫째 줄에 정수 \(H\), \(W\), \(N\)이 이 순서로 공백 하나로 구분되어 주어진다.
- 둘째 줄부터 \(H+1\)번째 줄까지, 각 줄에 S, 1, 2, \(\ldots\), 9, X, . 로 이루어진 길이 \(W\)의 문자열이 공백 없이 주어진다.
- 북쪽에서 \(i\)번째, 서쪽에서 \(j\)번째 칸을 \((i,j)\)라 하면(\(1 \le i \le H\), \(1 \le j \le W\)), \(i+1\)번째 줄의 \(j\)번째 문자는 칸 \((i,j)\)가 굴이면 S, 장애물이면 X, 빈터이면 ., 단단함 \(1, 2, \ldots, 9\)의 치즈를 만드는 공장이면 각각 \(1, 2, \ldots, 9\)이다.
- 입력에는 굴과 단단함 \(1, 2, \ldots, N\)의 공장이 하나씩 있다. 나머지 칸은 장애물 또는 빈터이다.
- 쥐는 모든 치즈를 먹을 수 있음이 보장된다.
- \(1 \le H \le 1000\)
- \(1 \le W \le 1000\)
- \(1 \le N \le 9\)
- 입력되는 수는 모두 정수이다.
출력
다음 형식으로 출력한다.
첫째 줄에 모든 치즈를 다 먹기까지 걸리는 가장 짧은 시간(분)을 출력한다.
예시 1
입력
3 3 1
S..
...
..1
출력
4
예시 2
입력
4 5 2
.X..1
....X
.XX.S
.2.X.
출력
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.......
출력
91