시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2.5 초 256 MB 140 57 42 50.000%

문제

디디학교 N명의 학생들은 N x M크기의 격자판에서 진행되는 장애물 달리기를 하려고 한다. 각 학생 i(i = 1, 2, 3, ..., N)는 처음에 (i, 1)의 위치에 서 있으며, 결승선 M열 즉, (1, M), (2, M), (3, M), ..., (N, M)의 어느 위치에라도 도착하는 것이 목표이다. 학생들은 한 번 이동할 때 상하좌우로 인접한 곳으로 이동하며, 각 위치로 이동하는 데 걸리는 시간은 같거나 다르다. 또한 학생들은 항상 결승선까지 가장 빨리 도착할 수 있는 경로로 이동한다. 교장선생님 디디는 결승선의 각 지점에 도착하는 학생 수만큼 생수를 배치하려고 한다. 이때 (i, M)에 각각 몇 개의 생수를 배치해야 하는 지 구하는 프로그램을 작성하라.

입력

첫째 줄에 격자판의 크기를 나타내는 NM(1 ≤ N, M ≤ 500)이 공백으로 구분되어 주어진다.

둘째 줄부터 N개의 줄에는 각각 M개의 정수가 공백으로 구분되어 주어진다. 입력의 i+1번째 줄의 j번째 정수는 격자판에서 (i, j)로 이동할 때 걸리는 시간을 의미하며, 이 값은 104 이하의 양의 정수이다. 단, i번째 학생이 이미 (i, 1)에 위치해 있으므로 시작 시 미리 밟고 있는 땅은 이동할 때 걸리는 시간에 포함되지 않지만, 결승선으로 이동하는 시간은 포함된다. 또한 한 학생이 가장 빨리 도착할 수 있는 도착지점은 유일하게 주어짐이 보장된다.

출력

첫째 줄부터 N개의 줄에 각각 (i, M)의 위치에 몇 개의 생수를 배치해야 하는지 출력하라.

예제 입력 1

4 4
3 4 5 2
1 6 2 8
1 3 4 5
6 2 1 10

예제 출력 1

1
0
3
0

힌트

각 학생은 아래와 같은 경로로 이동한다.

학생 1 : (1, 1) -> (1, 2) -> (1, 3) -> (1, 4)

학생 2 : (2, 1) -> (3, 1) -> (3, 2) -> (3, 3) -> (3, 4)

학생 3 : (3, 1) -> (3, 2) -> (3, 3) -> (3, 4)

학생 4 : (4, 1) -> (4, 2) -> (4, 3) -> (3, 3) -> (3, 4)

출처

Contest > 네블컵 > 제2회 네블컵 J번