编程实现:路径最小和
题目描述:
有一个N*M的矩阵方格,每个方格中都有一个正整数,现从左上角方格出发向右下角方格移动,每次只能向下或向右移动一个方格,请你找出一条最小路径,并输出该路径上的正整数之和。
最小路径:这条路径上的正整数之和最小。
例如:
N=2,M=3,2*3的矩阵方格中的正整数如下,
1 | 3 | 5 |
2 | 4 | 6 |
按照移动规则,从左上角方格移动到右下角方格的路径共3条,分别为1->3->5->6,1->3->4->6,1->2->4->6,3条路径上的正整数之和分别为15、14和13,其中正整数之和最小的一条路径是1->2->4->6,和为13,故输出13。
输入描述:
第一行输入两个正整数N和M(2≤N≤100,2≤M≤100),N表示矩阵方格的行数,M表示矩阵方格的列数,两个正整数之间以一个空格隔开
第二行开始输入N行,每行M个正整数(1≤正整数≤200),正整数之间以一个空格隔开
输出描述:
输出一个整数,表示最小路径上的正整数之和
样例输入:
2 3
1 3 5
2 4 6
样例输出:
13
测试用例:
输入 | 2 3 1 2 3 4 5 6 | 3 3 1 3 1 1 5 1 4 2 1 | 4 8 2 7 3 4 1 5 9 6 9 8 7 6 5 4 3 2 3 4 2 1 7 4 5 3 8 7 2 4 1 2 6 3 | 6 9 9 8 7 6 5 4 3 2 1 1 3 1 6 5 4 3 2 6 1 6 5 4 3 2 2 6 9 2 4 47 2 4 1 2 6 1 2 5 2 7 2 4 1 2 6 5 8 2 7 3 4 5 9 4 | 10 15 3 4 1 7 4 5 2 8 7 2 4 23 12 12 34 13 41 11 71 14 15 12 81 17 12 14 23 12 12 34 32 42 21 27 42 5 22 8 27 2 4 23 12 12 34 13 4 1 37 4 35 32 8 7 23 4 13 7 43 53 53 45 22 14 72 44 52 39 29 58 28 78 22 42 18 12 6 3 22 51 2 71 2 4 13 2 56 5 22 8 58 37 46 25 14 73 42 51 30 22 71 34 13 23 62 12 25 21 9 8 77 26 57 4 63 12 71 21 27 62 17 6 52 4 23 2 22 6 9 22 5 2 77 21 24 22 52 12 47 52 64 11 76 5 74 53 24 24 61 29 |
输出 | 12 | 7 | 37 | 44 | 247 |