#7803. 路径最小和 入门

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

有一个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(2ENE100.2EME100)。N表示矩阵方格的行数。M表示矩阵方格的列数,两个正整数之间以一个空格隔开
第二行开始输入N行,每行M个正整数(1每正整数=200)。正整数之间以一个空格限开
输出描述
输出一个整数,表示最小路径上的正整数之和
样例输入
23 135 246 样例输出13

第二行开始输入N行,每行M个正整数(1<=正整数<=200)。正整数之间以一个空格隔开
输出描述
输出一个整数,表示最小路径上的正整数之和
样例输入
2 3
1 3 5
2 4 6
样例输出
13

输入格式

第一行输入两个正整数N和M(2<N<100,2<M<100)。
N表示矩阵方格的行数,M表示矩阵方格的列数,两个正整数之间以一个空格隔开。

第二行开始输入N行,每行M个正整数(1<= M <=200)。
正整数之间以一个空格隔开。

输出格式

输出一个整数,表示最小路径上的正整数之和。

样例

样例输入1

2 3
1 3 5 
2 4 6

样例输出1

13