题库 蓝桥杯青少组题库 题目列表 编程实现:路径最小和题目描述:有一个N*M的矩阵方格...
问答题

编程实现:路径最小和

题目描述:

有一个N*M的矩阵方格,每个方格中都有一个正整数,现从左上角方格出发向右下角方格移动,每次只能向下或向右移动一个方格,请你找出一条最小路径,并输出该路径上的正整数之和。

 

最小路径:这条路径上的正整数之和最小。 

                 

例如:

N=2,M=3,2*3的矩阵方格中的正整数如下,

135
246


按照移动规则,从左上角方格移动到右下角方格的路径共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

题目信息
创意编程组 第十四届 STEMA 中级 高级
-
正确率
0
评论
176
点击