【蓝桥杯选拔赛真题55】C++最长路线 第十四届蓝桥杯青少年创意编程大赛 算法思维 C++编程选拔赛真题解

目录

C++最长路线

一、题目要求

1、编程实现

2、输入输出

二、算法分析

三、程序编写

四、程序说明

五、运行结果

六、考点分析

七、推荐资料

C++最长路线

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

一、题目要求

1、编程实现

有一个N*M的矩阵，且矩阵中每个方格中都有一个整数(0≤整数≤100)，小蓝需要按照以下要求从矩阵中找出一条最长的移动路线，且输出最长路线的长度(1个方格为1个长度)。
要求:

1. 小蓝可以从矩阵中任意一个方格开始向它的上、下、左、右相邻的任意一个方格移动，且移动的路线不能有交叉:
2. 小蓝每次所要移动到的方格中的整数都要小于当前所在方格中的整数(如当前所在的方格中的整数为3，那么可以移动到数字为0，1，2的格子里不可以移动到数字为3，4，5.的格子里);

例如:N=3，M=3，矩阵方格如下：

最长路线为4->3->2->1，故路线长度为4。

2、输入输出

输入描述：第一行输入两个正整数N，M(1<N≤1000，1<M≤1000)，N表示矩阵的行数，M表示矩阵的列数，两个正整数之间以一个空格隔开
第二行开始输入N行，每行包含M个整数(0s每个整数≤100)，表示每个方格中的整数，每个整数之间以一个空格隔开

输出描述：输出一个整数，表示最长路线的长度

输入样例：

3 3
1 1 3
2 3 4
1 1 1

输出样例：

4

二、算法分析

1. 从给定题目的初步分析可以看出，程序是一个二维矩阵题目
2. 题目是要根据当前所在位置对应的上下左右四个方向的值进行判定走向
3. 走到下一个值的时候同样要进行四个方向的值的判定
4. 所以可以采用深度优先算法进行实现，递归函数就是返回上下左右四个方向上最大的那个值加1，之所以加1，是因为走了一步，所以步数加1

三、程序编写

#include<iostream>
using namespace std;
const int M = 1005;
int n,m,a[M][M],f[M][M];

int dfs(int i,int j)
{
	int up,down,left,right;
	if(f[i][j] == 0)
	{
		up = (i-1 >= 0 && a[i-1][j] < a[i][j])?dfs(i-1,j):0;
		down = (i+1 < n && a[i+1][j] < a[i][j])?dfs(i+1,j):0;
		left = (j-1 >= 0 && a[i][j-1] < a[i][j])?dfs(i,j-1):0;
		right = (j+1 < m && a[i][j+1] < a[i][j])?dfs(i,j+1):0;	
		f[i][j] = max(max(max(up,down),left),right) + 1;
	}
	return f[i][j];
}
int main()
{
	int maxlen = 0;
	cin >> n >> m;
	for(int i = 0;i < n;i++)
		for(int j = 0;j < m;j++)
			cin >> a[i][j];
			
	for(int i = 0;i < n;i++)
		for(int j = 0;j < m;j++)
			maxlen = max(dfs(i,j),maxlen);	
	cout << maxlen << endl;
}

四、程序说明

1. 首先需要导入输入输出流头文件
2. 然后是引入std命名空间中的所有成员到当前的程序中，这样在当前的程序中就可以直接使用 std 命名空间中的所有成员，而不需要使用的时候在成员前面加上（std::）前缀
3. 程序定义了一个常量M，用来表示矩阵的最大尺寸
4. 接着定义了变量n和m，分别表示矩阵的行数和列数；定义了一个二维数组a，用来存储矩阵中的值。 同时，定义了一个二维数组f，用来存储从每个点出发的最长递增路径的长度
5. 接下来，就是深度优先算法函数dfs，用来计算从某个点出发的最长递增路径的长度。 在dfs函数中，首先判断f[i][j]是否已经计算过，如果计算过，直接返回f[i][j]
6. 如果f[i][j]未计算过，就按照上、下、左、右四个方向进行递归调用dfs函数，并更新f[i][j]的值
7. 最后，主函数中先读入矩阵的行数和列数，然后读入矩阵的值
8. 接着，利用两个嵌套循环遍历矩阵的每一个点，并调用dfs函数计算最长递增路径的长度，并更新maxlen的值
9. 然后输出maxlen的值，即矩阵中最长递增路径的长度
10. 最后返回0，程序结束

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

五、运行结果

3 3
1 1 3
2 3 4
1 1 1

4

六、考点分析

难度级别：难，这题相对而言还是有一定的难度，难在题目分析和算法设计，具体主要考查如下：

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

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

七、推荐资料

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