蓝桥等考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套)