Informatica Online Judge

  최소 가중치 이동 [1307 / 051B]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 21   Total Tried : 31


The Champion of this Problem (C++) : gs15088 - 0ms / 516byte
My Best Submission (C++) : N/A

[Programming Challenges 111104]

Background

정수로 된 n*m 배열이 있다.

이 배열은 현재 지도를 추상화한 것인데, 각 값은 현재 위치의 위험도를 나타낸다.

경곽이는 이 지도상의 왼쪽 어딘가에서 출발하여 오른쪽 어딘가로 탈출할 수 있다.

경곽이가 이동할 수 있는 방법은 다음 그림과 같다.



그리고 특이한 사항은 가장 아래쪽 칸에서 더 내려가면 가장 위 칸이 된다. 즉, 실제 땅은 원통형으로 생겼다. (지구는 구지만 구는 아니고 원통이다.)

따라서 1번에서 위쪽으로 이동하며 n이 되고 n에서 아래쪽으로 이동하면 1이 된다.

다음 예를 보면 쉽게 이해할 수 있다. 다음은 서로 다른 2개의 지도를 보여준다.

각 이동 경로는 가장 적은 위험도를 가지는 곳으로 이동하는 경우를 나타낸다.



이 문제의 목적은 경곽이가 이 맵을 탈출하는데 위험도를 최소화 하는 것이다.

그리고 그 경로도 구해야 한다. 이를 해결할 수 있는 프로그램을 작성하시오.

Input

첫 번째 줄에 맵의 행의 크기 n과 열을 크기 r이 주어진다.

그리고 두 번째 줄부터 n줄에 걸쳐서 각 줄에 m개의 자연수가 공백으로 구분되어 입력된다. 이 값들은 현재 위치의 위험도를 나타낸다.

[입력값의 정의역]
1 <= n <= 10
1 <= m <= 1,000
1 <= 위험도 <= 1,000

Output

첫 번째 줄에 탈출 경로를 m개 출력한다.

이 값은 1열부터 m열에 걸쳐서 탈출할 때 각각 어떤 행을 지나는지를 나타낸다.

만약 같은 위험도가 여러 개 존재한다면 경로를 사전순으로 정렬했을 때, 가장 먼저 나타나는 값을 출력한다.

그리고 두 번째 줄에는 최소 위험도 값을 출력한다.

IO Example

입력1
5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 8 6 4

출력1
1 2 3 4 4 5
16

입력2
5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 1 2 3

출력2
1 2 1 5 4 5
11

* 설명 : 각 입력1, 입력2는 위 그림의 왼쪽과 오른쪽에 대응된다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]