蓝桥等考C++组别十一级
第一部分：选择题
第二部分：编程题
5
、
C++ L11
路径上数字的最
小
和（
3
0分）
题目名称：
路径上数字的最小和
题目描述：
给定一个整数方阵，在某一列从第一行到最后一行画一条路径，再将路径的两端分别连接左上角元素和右下角元素。请找出从左上角元素到右下角元素的所有路径上数字和的最小值。
例如，一个
4
*4
的方阵
为：
1
2
3
4
6
7
8
1
5
4
3
2
1
3
6
9
可以发现，在黄色路径上数字和的最小值为
22
。
1
2
3
4
6
7
8
1
5
4
3
2
1
3
6
9
输入：
第
1
行
是
1
个整数n，
表示矩阵的行数和列数（
2
<
=
n <
=
2
0）。
接下来的
n
行为
n *
n
的
方
阵，其中每行有
n
个用单个空格隔开的非负整数
（0
~9
）
。
输出：
输出
1
个个整数，表示矩阵从左上角元素到右下角元素的所有路径上数字和的最小值。
输入样例：
4
1 2 3 4
6 7 8 1
5 4 3 2
1 3 6 9
输出样例：
22
参考程序：
#include<iostream>
using namespace std;
const int N = 50;
int a[N+1][N+1];
int main()
{
int n, minsum = 100000000;
cin >> n;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
cin >> a[i][j];
}
}
for (int i = 1; i <= n; i++)
{
int sum = 0;
for (int j = 1; j <= i; j++)
{
sum += a[1][j];
}
for (int j = 2; j < n; j++)
{
sum += a[j][i];
}
for (int j = i; j <= n; j++)
{
sum += a[n][j];
}
minsum = min(minsum, sum);
}
cout << minsum;
return 0;
}
测试数据：
1.in
4
1 2 3 4
6 7 8 1
5 4 3 2
1 3 6 9
1.out
22
2.in
5
5 2 0 9 7
2 4 5 5 8
1 9 6 5 7
9 6 0 4 6
6 9 3 0 7
2.out
28
余下略，见附件目录下
testcase.txt
蓝桥杯青少组C++组别11级编程练习真题（第10套，共10套）