编程实现:
路径最小和
题目描述:
有一个N*M的矩阵方格,每个方格中都有一个正整数,现从左上角方格出发向右下角方格移动,每次只能向下或句右移动一个方格,请你找出一条最小路径、并输出该路径上的正整数之和。
最小路径:这条路径上的正整数之和最小。
例如:
N=2、M=3。2*3的矩阵方格中的正整数如下,按照移动规则,从左上角方格移动到右下角方格的路径共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