문제1218--경로 합이 최소인 경로 찾기

1218: 경로 합이 최소인 경로 찾기

시간제한 : 1.000 sec  메모리제한 : 128 MB

문제 설명

m x n 그리드가 주어집니다. 각 셀에 0 이상의 수가 주어집니다.  가장 왼쪽 위 셀에서 가장 오른쪽 아래 셀까지 가는 경로 중 합계가 가장 작은 경로를 찾아주세요. 이동은 한 번에 오른쪽 또는 아래 셀로 이동할 수 있습니다.
예를 들어 3x3 셀이 다음과 같이 주어지면 합이 최소인 경로는 1 -> 3 -> 1 -> 1 -> 1이고 그것의 합은 7입니다.
1 3 1
1 5 1
4 2 1

입력 설명

첫 줄에는 테스트케이스 T(1<=T<=100)가 주어집니다. 각 테스트케이스마다 첫 줄에는 그리드의 행 M(1<=M<=200)과 열 N(1<=N<=200)이 주어집니다. 그다음부터 M줄에 각 그리드의 행 정보를 나타내는 N개 정수 X(0<=X<=100)가 주어집니다.

출력 설명

각 테스트케이스마다 경로의 합이 최소가 되는 경로를 찾고, 그 경로의 합을 출력하여 주세요.

입력 예시 Copy

2
3 3
1 3 1
1 5 1
4 2 1
2 3
1 2 3
4 5 6

출력 예시 Copy

7
12

출처/분류