제리의 치즈먹기 (Cheese)

올해도 톰이 운영하는 치즈 공장이 치즈 생산을 시작하자, 생쥐 제리가 둥지에서 얼굴을 내밀었다.

톰과 제리가 사는 ‘치즈피아’ 시는 동서남북으로 구획 정리되어 있고, 각 구획은 제리의 둥지, 치즈 공장, 장애물 공터 중 하나이다.

제리는 둥지에서 출발하여 모든 치즈 공장을 방문하여 치즈를 1 개씩 먹는다.

‘치즈피아’ 시에는 N 개의 치즈 공장이 있고, 어떤 공장도 1 종류의 치즈만을 생산하고있다.

치즈의 딱딱한 정도는 공장에 따라 다르고 딱딱한 정도 1에서 N까지의 치즈를 생산하는 치즈 공장이 각각 하나씩만 있다.

제리의 첫 번째 체력은 1 이며, 치즈를 1 개 먹을 때마다 체력이 1 증가한다. 그러나 제리는 자신의 체력보다 딱딱한 치즈를 먹을 수 없다.

생쥐 제리는 동서남북에 인접한 부지로 이동하는데 1분이 걸린다. 하지만 인접한 부지가 장애물인 경우 인접한 부지에 들어갈 수 없다.

인접한 부지가 치즈 공장인 경우에는 그 공장의 치즈를 먹지 않고 지나갈 수도 있다.

모든 치즈를 먹고 끝내는 데 걸리는 최소 시간을 구하는 프로그램을 작성하라.

생쥐 제리가 치즈를 먹는 데 걸리는 시간은 무시할 수 있을 만큼 짧다.

입력

입력은 H + 1 행으로 이루어진다. 첫 번째 행에는 세 개의 정수 H, W, N (1 <= H <= 1000, 1 <= W <= 1000, 1 <= N <= 9)이 공백으로 구분하여 주어진다.

두 번째 줄에서 H + 1 번째 줄 까지의 각 행에는 'S', '1', '2', ..., '9', 'X', '.'로 이루어진 W개의 문자열이 주어지며, 각각의 문자는 각 영역의 상태를 나타낸다.

제리의 둥지인 경우 'S'이고, 장애물 인 경우 'X', 공터이면 '.'가 되고, 치즈를 생산하는 공장인 경우는 각각 '1', '2', ..., '9'가 된다. 각 숫자는 딱딱한 정도를 나타낸다.

입력 데이터에는 제리의 둥지 ‘S’와 치즈를 생산하는 공장 1, 2, ..., N 이 각각 하나 씩 있다.

쥐는 모든 치즈를 먹을 수 있는 것이 보장되어 있다.

출력

제리가 모든 치즈를 체력에 맞추어 먹고 끝내는 데 걸리는 최소 시간 (분)을 나타내는 정수를 한 줄로 출력하라.

예제1

예제2

예제3

출처

joi 2010/2011 예선 5

제리의 치즈먹기 (Cheese) 1000초 128MB