장애물 달리기
시간 제한2.5초메모리 제한256 MB
각 행의 출발점에서 마지막 열의 최단 도착점까지 이동하는 최단 경로 K개를 구해, 각 도착 셀에 도착하는 학생 수를 구합니다.
문제
디디학교 N명의 학생이 N x M 크기의 격자판에서 장애물 달리기를 하려고 한다. 각 학생 i(i = 1, 2, 3, ..., N)는 처음에 (i, 1)에 서 있고, 결승선인 M열, 즉 (1, M), (2, M), (3, M), ..., (N, M) 중 어느 위치에든 도착하는 것이 목표이다. 학생은 한 번 이동할 때 상하좌우로 인접한 곳으로 이동하며, 각 위치로 이동하는 데 걸리는 시간은 같을 수도 있고 다를 수도 있다. 학생은 항상 결승선까지 가장 빨리 도착할 수 있는 경로로 이동한다. 교장선생님 디디는 결승선의 각 지점에 도착하는 학생 수만큼 생수를 배치하려고 한다. (i, M)에 각각 몇 개의 생수를 배치해야 하는지 구하는 프로그램을 작성하라.
입력
첫째 줄에 격자판의 크기를 나타내는 N, M(1 ≤ N, M ≤ *500)이 공백으로 구분되어 주어진다.
둘째 줄부터 N개의 줄에는 각각 M개의 정수가 공백으로 구분되어 주어진다. 입력의 i+1번째 줄의 j번째 정수는 격자판에서 (i, j)로 이동할 때 걸리는 시간을 의미하며, 이 값은 104 이하의 양의 정수이다. 단, i번째 학생이 이미 (i, 1)에 위치해 있으므로 시작 시 미리 밟고 있는 땅은 이동할 때 걸리는 시간에 포함되지 않지만, 결승선으로 이동하는 시간은 포함된다. 또한 한 학생이 가장 빨리 도착할 수 있는 도착지점은 유일하게 주어짐이 보장된다.
출력
첫째 줄부터 N개의 줄에 각각 (i, M)의 위치에 몇 개의 생수를 배치해야 하는지 출력하라.
힌트
각 학생은 아래와 같은 경로로 이동한다.
학생 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)