备战蓝桥杯——算法训练之过河马

xorpay 发布于2021-11-15 11:38 / 3082人阅读

摘要：而众所周知，马是要走日子格的。输出格式输出有一行，一个数表示走法数。那为了防止爆掉，我们每加完一条路的总步数之后就取一遍余。题目解法思路如上述，但是这里有一个我之前从来没有注意过的问题，导致我一直只有分。三题解四题目链接过河马

算法训练之过河马

一、题目
二、思路
三、题解
四、题目链接

一、题目

资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
　　在那个过河卒逃过了马的控制以超级超级多的走法走到了终点之后，这匹马表示它不开心了……
　　于是，终于有一天，它也过河了！
　　由于过河马积累了许多的怨念，所以这次它过了河之后，再也没有什么东西可以限制它，它可以自由自在的在棋盘上驰骋。一开始，它是在一个n行m列棋盘的左下角（1,1）的位置，它想要走到终点右上角（n，m）的位置。而众所周知，马是要走日子格的。可是这匹马在积累了这么多怨念之后，它再也不想走回头路——也就是说，它只会朝向上的方向跳，不会朝向下的方向跳。
　　那么，这匹马它也想知道，它想从起点跳到终点，一共有多少种走法呢？
输入格式
　　第一行两个数n，m，表示一个n行m列的棋盘，马最初是在左下角（1,1）的位置，终点在右上角（n，m）的位置。
输出格式
　　输出有一行，一个数表示走法数。由于答案可能很大，所以输出答案除以1000000007所得的余数即可。
样例输入
4 4
样例输出
2
数据规模和约定
　　n<=100,m<=100

二、思路

如图，我们理一下思路，从左下角跳到右上角，用一个二维数组来存储跳到每个点的总步数。我们来逆推，（其中2,3和3,2只可能是从1,1跳来的。），以黄点为例，他可能是A、B、C、D任意一点跳来的。然后，要判断一下A、B、C、D在不在棋盘内。
然后题目说答案可能很大，输出答案除以1000000007所得的余数即可。那为了防止爆掉，我们每加完一条路的总步数之后就取一遍余。
题目解法思路如上述，但是这里有一个我之前从来没有注意过的问题，导致我一直只有90分。那就是我一直习惯于在main函数内声明变量。。。
具体原因是在这篇博客里看的，详情点击传送门。
其实就是说在main函数外面开一个数组，他的内存分配在数据区里；如果在main函数内部开数组，内存分配在栈区内。一般来说栈区的内存是比较小的，所以平常开一些小一点的数组是没问题的；但如果题目要求的数组比较大，那就会出现爆出的问题。

三、题解

#includeusing namespace std;int n,m;int cb[105][105];int main(){	cin>>n>>m;	cb[2][3] = cb[3][2] = 1;	for(int i = 1;i <= n;i++)	{				for(int j = 1;j <= m;j++)		{			if(i-1 >=1 && j-2 >= 1)			{				cb[i][j] += cb[i-1][j-2];				cb[i][j] %= 1000000007;			} 			if(i-2 >=1 && j-1 >= 1)			{				cb[i][j] += cb[i-2][j-1];				cb[i][j] %= 1000000007;			} 			if(i-2 >=1 && j+1 <= m)			{				cb[i][j] += cb[i-2][j+1];				cb[i][j] %= 1000000007;				} 			if(i-1 >=1 && j+2 <= m)			{				cb[i][j] += cb[i-1][j+2];				cb[i][j] %= 1000000007;				} 		}	}	cout<<cb[n][m];	return 0;}

四、题目链接

ALGO-981 过河马

GPU云服务器云服务器蓝桥杯届蓝桥杯蓝桥杯省赛 Java?蓝桥杯

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/123334.html

蓝桥杯算法训练审美课 java

摘要：问题描述审美的历程课上有位学生，帅老师展示了幅画，其中有些是梵高的作品，另外的都出自五岁小朋友之手。输入格式第一行两个数和，表示学生数和图画数接下来是一个的矩阵如果，表示学生觉得第幅画是小朋友画的如果，表示学生觉得第幅画是梵高画的。问题描述　　《审美的历程》课上有n位学生，帅老师展示了m幅画，其中有些是梵高的作品，另外的都出自五岁小朋友之手。老师请同学们分辨哪些画的作者是梵高，但是老...

worldligang 2019-08-16 15:36 评论0 收藏0
2021蓝桥杯你值得拥有

摘要：文章目录一你应该知道的蓝桥杯含金量获奖率高不高支持哪些编程语言二川川带你体验蓝桥杯省赛蓝桥杯蓝桥杯三个人感受一你应该知道的蓝桥杯如果你是计算机相关专业，你不知蓝桥杯就过不去了，我们来看看蓝桥杯如何，不知道更应该来了解下了。 ...

fanux 2021-11-18 10:02 评论0 收藏0
2018第九届蓝桥杯Java b组总结

摘要：现在小明想统计有哪些帖子曾经是热帖。如果一个帖子曾在任意一个长度为的时间段内收到不少于个赞，小明就认为这个帖子曾是热帖。以下行列代表一张海域照片。照片保证第行第列第行第列的像素都是海洋。 2018年4月1日愚人节，我第一次参加了有关计算机算法类比赛蓝桥杯，这篇算是经验总结和题目回顾，水平有限，有不妥之处欢迎留言批评指正，也可以加QQ891465170交流~下面进入正题：第一题：第几...

codecook 2019-08-15 15:11 评论0 收藏0
【两万字精编~建议抱走】蓝桥杯算法竞赛系列第0章——蓝桥必考点及标准模板库STL（下）

摘要：时间复杂度为，和分别是和的长度示例如下输出输出把从号位开始长度为的子串替换为上把的迭代器范围的子串替换为示例如下欢迎回到：遇见蓝桥遇见你，不负代码不负卿！目录【补充】：常用头文件及库函数 1.#include sscanf() 和 sprintf() 2.#include 3.#...

sixleaves 2021-11-22 09:34 评论0 收藏0
蓝桥杯-乌托邦树

摘要：传送门题目描述实现一个算法得到乌托邦树的高度介绍如下乌托邦树每年经历个生长周期。每年夏天，它的高度都会增加米。对于一颗在春天开始时种下的高米的树，问经过指定周期后，树的高度为多少。输入描述输入一个数字，表示指定周期。 ...

caiyongji 2021-11-22 09:34 评论0 收藏0