【蓝桥杯选拔赛真题40】C++路径最小和 第十四届蓝桥杯青少年创意编程大赛 算法思维 C++编程选拔赛真题解析

目录

C++路径最小和

一、题目要求

1、编程实现

2、输入输出

二、算法分析

三、程序编写

四、程序说明

五、运行结果

六、考点分析

七、推荐资料

---

C++路径最小和

第十四届蓝桥杯青少年创意编程大赛C++选拔赛真题

一、题目要求

1、编程实现

有一个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。

2、输入输出

输入描述：第一行输入两个正整数N和M(2≤N≤100，2≤M≤100)，N表示矩阵方格的行数，M表示矩阵方格的列数，两个正整数之间以一个空格隔开
第二行开始输入N行，每行M平整数(1≤正整数≤200)。正整数之间以一个空格隔开

输出描述：只有一行，一个整数，即最小路径上的正整数之和

输入样例：

2 3
1 3 5
2 4 6

输出样例：

13

二、算法分析

1. 从给定题目的初步分析可以看出，这是一个比较典型的求最短路径和问题
2. 这个问题解法有多种，但是如果小朋友们没有接触过算法，可能会有点无从下手
3. 小兔子老师这里采用小朋友能比较好理解的一种递归函数求解
4. 求解的思路是：在每一次递归中，函数会判断当前位置是否越界，如果越界则返回。
5. 否则，将当前位置加入路径和sum中，并判断是否到达了右下角。
6. 如果到达右下角，将当前路径和sum与之前的最小路径和res进行比较，并更新最小路径和。
7. 然后，分别递归地向右和向下移动，继续搜索。
8. 最后就得到我们要求的最小路径和
9. 注：这种方法对小朋友来说是比较好理解，但是解题的时间复杂度可能是比较大的为：2^(n*m)，往往可能会出现超时的情况，更好的方式是采用动态规划的方式求解，欢迎小朋友进行互动，小朋友们可以自己探索下哦

三、程序编写

#include <iostream>
using namespace std;
int n,m,res,a[105][105];
void minPath(int i,int j,int sum)
{
	if(i<0 || j<0 || i>=n || j>= m)
		return ;
	sum += a[i][j];
	if(i == n-1 && j == m-1)
	{
		res = min(res,sum);
		return;
	}
	minPath(i,j+1,sum);
	minPath(i+1,j,sum);
}
int main() 
{
	res = 1e8;
	cin >> n >> m;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			cin >> a[i][j];
	minPath(0,0,0);
	cout << res;
    return 0;
}

四、程序说明

1. 首先需要导入输入输出流头文件
2. 接着再次导入输入输出流格式控制头文件
3. 然后是引入std命名空间中的所有成员到当前的程序中，这样在当前的程序中就可以直接使用 std 命名空间中的所有成员，而不需要使用的时候在成员前面加上（std::）前缀
4. 然后定义了全局变量n和m，分别表示矩阵的行数和列数。
5. 定义了全局变量res，用来记录最小路径和的结果。
6. 定义了二维数组a，表示存储矩阵的值。
7. 定义了一个minPath函数，用来递归计算矩阵的最小路径和。该函数接受三个参数：当前位置的行号i、当前位置的列号j、当前已走过的路径和sum。
8. 在minPath函数中，首先判断是否越界，如果越界则直接返回。
9. 累加当前位置的值到sum中。
10. 判断是否到达矩阵的最后一个位置，如果是则更新res为当前sum和res的较小值，并返回。
11. 递归调用minPath函数，向右和向下两个方向继续搜索。即调用minPath(i, j+1, sum)和minPath(i+1, j, sum)。
12. 在main函数中，首先将res初始化为一个较大的值1e8（即10^8）。
13. 输入矩阵的行数和列数。
14. 使用嵌套循环读取矩阵的每个元素。
15. 调用minPath函数，从矩阵的起点开始搜索最小路径和。
16. 输出结果res，即最小路径和。
17. 最后程序结束

 本文作者：小兔子编程 作者首页：https://blog.csdn.net/frank2102

五、运行结果

2 3
1 3 5
2 4 6

​13

六、考点分析

难度级别：难，这题相对而言还是有点难度的，具体主要考查如下：

1. 充分掌握变量的定义和使用
2. 充分掌握递归函数、动态规划等算法的求解过程
3. 学会输入流对象cin的使用，从键盘读入相应的数据
4. 学会for循环的使用，在确定循环次数的时候推荐使用学会
5. 学会while循环的使用，在不确定循环次数的时候推荐使用
6. 学会if条件判断语句的使用，满足一定条件才能执行后面的语句
7. 学会if...else...双分支语句的使用，条件满足执行一种处理，不满足执行另一种处理
8. 学会fixed与setprecision函数结合使用是保留小数点后的位数，小数点的保留采用四舍五入
9. 掌握输出流对象cout的使用，与流插入运算符 << 结合使用将对象输出到终端显示
10. 学会分析题目，算法分析，将复杂问题模块化，简单化，从中找到相应的解题思路
11. 充分掌握变量定义和使用、分支语句、循环语句和简单算法知识的使用及输入输出的用法

PS：方式方法有多种，小朋友们只要能够达到题目要求即可！

七、推荐资料

• 所有考级比赛学习相关资料合集【推荐收藏】