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

C++最长路线

一、题目要求

1、编程实现

2、输入输出

二、算法分析

三、程序编写

四、程序说明

五、运行结果

六、考点分析

七、推荐资料

C++最长路线

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

一、题目要求

1、编程实现

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

小蓝可以从矩阵中任意一个方格开始向它的上、下、左、右相邻的任意一个方格移动，且移动的路线不能有交叉:
小蓝每次所要移动到的方格中的整数都要小于当前所在方格中的整数(如当前所在的方格中的整数为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)，表示每个方格中的整数，每个整数之间以一个空格隔开

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

输入样例：

输出样例：

二、算法分析

从给定题目的初步分析可以看出，程序是一个二维矩阵题目
题目是要根据当前所在位置对应的上下左右四个方向的值进行判定走向
走到下一个值的时候同样要进行四个方向的值的判定
所以可以采用深度优先算法进行实现，递归函数就是返回上下左右四个方向上最大的那个值加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;
}

四、程序说明

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

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