erick12   2년 전

번역기 기반으로 번역해봤습니다

문제

올해도 A마을의 치즈 공장이 치즈 생산을 시작했고, 마을에 사는 쥐가 둥지에서 나와 돌아다니기 시작했다. A마을은 동서남북 격자 모양으로 생겼으며, 각 구역은 쥐 둥지, 치즈 공장, 장애물, 빈 땅 중 하나이다. 쥐는 둥지에서 출발하여 모든 치즈 공장을 방문하여 치즈를 하나씩 먹는다.

이 마을에는 N 개의 치즈 공장이 있으며 모든 공장은 하나의 치즈만 생산한다. 치즈의 경도는 공장마다 다르며, 경도 1에서 N까지의 치즈를 생산하는 치즈 공장이 정확히 하나씩 있다.

쥐가 둥지에서 출발할 때의 체력은 1이며, 치즈를 1개 먹을 때마다 체력이 1 증가한다. 그러나 쥐는 자신의 체력보다 딱딱한 치즈를 먹을 수 없다.

쥐는 동서남북에 인접한 구역으로 1분 동안 이동할 수 있지만 장애물 구역에는 들어갈 수 없다. 치즈 공장을 치즈를 먹지 않고 지나갈 수도 있다. 모든 치즈를 먹기까지 걸리는 최단 시간을 요구하는 프로그램을 써라. 그러나 쥐가 치즈를 먹는 데 걸리는 시간은 무시할 수 있다.

입력

입력은 H + 1줄로 구성되어 있다. 첫번째 줄에는 에는 정수 H, W, N (1 ≤ H ≤ 1000, 1 ≤ W ≤ 1000, 1 ≤ N ≤ 9)이 이 순서로 공백으로 구분되어 쓰여져 있다. 그 뒤 H행에는 'S', '1', '2', ..., '9', 'X', '.' 로 이루어지는 길이가 W인 문자열이 쓰여져 있으며 각각은 각 구역의 상태를 나타낸다. 북에서 i번째, 서쪽에서 j번째의 구역을 (i, j)라고 하면(1≤i≤H, 1≤j≤W), i+1번째 줄의 j번째의 문자는 구역 (i, j)이 둥지인 경우는 'S'가 되고, 장애물인 경우는 'X'가 되어, 빈 땅인 경우는 '.'가 되며, 경도 1, 2, ..., 9 치즈를 생산하는 공장인 경우는 각각 '1', '2', ..., '9'가 된다. 입력에는 둥지와 경도 1, 2, ..., N의 치즈를 생산하는 공장이 각각 하나씩 있다. 다른 구역은 장애물이나 빈 곳임이 보장된다. 쥐는 모든 치즈를 먹을 수 있다는 것이 보장된다.

출력

모든 치즈를 먹기까지 걸리는 최단 시간(분)을 나타내는 정수를 한 줄로 출력하라.

댓글을 작성하려면 로그인해야 합니다.