当前位置:首页 > 题解目录 > 正文内容

【题解】上学线路(2019青岛市程序设计比赛)

亿万年的星光4年前 (2021-04-16)题解目录2431

 【题目描述】

D从家到学校的道路结构是这样的:由n条东西走向和m条南北走向的道路构成了一个n*m的网格,每条道路都是单向通行的(只能从北向南,从西向东走)。

已知小D的家在网格的左上角,学校在网格的右下角。

问小D从他的家到学校一共有多少种不同的上学路线?

【输入格式】

两个正整数n,m,意义如前所述。

【输出格式】

D上学路线数量。结果对1000000007取余。

【输入输出样例】

roud.in

roud.out

3 4

10

【数据规模和约定】

50%的数据:n,m<=20

100%的数据: n,m<=1000

【来源】

2019年青岛市程序设计竞赛试题(小学组)1T

【题目分析】

  • 一个比较典型的DFS题目,跟“马拦过河卒”有点像。

  • 只能从北往南,从西往东走,不能走回头路。

  • 整个图的大小是由m和n决定的,比较坑的是题目中n*m的隐含意思是从(1,1)点开始(不然样例计算出是35)。



【参考代码1】——DFS没有优化

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m; //定义B点坐标和马的坐标
int dx[2]= {0,1}; //x变化
int dy[2]= {1,0}; //y变化
bool flag[16][16]; //标记数组,用来标记哪些点能走或不能走
int sum; //定义总路径条数

//使用框架二
void dfs(int sx,int sy) {
	if(sx==n && sy==m) {
		sum++;  //到达b点就累加1
		return;
	}
	for(int i=0; i<2; i++) { //两种走法(下,右)
		int fx=sx+dx[i]; //某一方向的x坐标
		int fy=sy+dy[i]; //某一方向的y坐标
		if(flag[fx][fy]==0 && fx<=n && fy<=m) {  
			flag[fx][fy]=1; //将当前点变为1,表示此点已经走过了 
			dfs(fx,fy);     //继续遍历下一个点 
			flag[fx][fy]=0; //回溯一步 
		}
	}

}
int main() {
	cin>>n>>m; //读入n和m; 
	dfs(1,1); //从0,0开始遍历,
	cout<<sum%1000000007<<endl;
	return 0;
}



【后续优化】

可以使用

  • (a + b) % p = (a%p + b%p) %p

优化


【参考代码2】——数学关系(二维数组+递推)

如果上面的DFS感觉比较难,还有一个数学的思路可以用。

假设每个单元格的距离都是1,那么A->B1的走法是1种,A->C1的走法也是1种。

我们看一下A->D的走法有多少种。答案是2种,分别是从B1->D和从C1->D。(记住:B1和C1的走法已经确定了,这非常重要)

----------------------------------------

再来看A-G的走法。G点只能由D点和C2点走过来,D点的走法上面已经确定了(2种),从A到C2点只有一种走法,所以是2+1=3种。

可以得出结论:每个点的走法种数=这个点上方的种数+这个点左侧的种数。

也就是二维数组  a[i][j]=a[i-1][j]+a[i][j-1]

注意边界点即可。




扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

【题解】区间和

1.区间和(sum.cpp)【描述】输入一个整数Q,进行Q次询问,每次给定两个整数l和r,每一次输出l~r中所有平方数的和 % 1000000007【输入】第一行是一个整数Q后面的Q行每行有...

【题解】2002-T2 选数

【题解】2002-T2 选数

【题目描述】已知n个整数x1,x2,……xn,以及一个整数K(K<n)。从n个整数中任选k个整数相加,可分别 得到一系列的和。例如当n=4, =3, 4个整数分别为3,7,12,1...

【题解】凯撒密码

【题目描述】恺撒生活在充满危险和阴谋的时代. 恺撒面对的最困难的问题是生存. 为了生存, 他决定创造一种密码. 这种密码听起来难以置信, 如果不知道方法, 没有人可以破解.你是恺撒军队的一个上尉. 你...

【题解】金银岛

题目描述某天KID利用飞行器飞到了一个金银岛上,上面有许多珍贵的金属,KID虽然更喜欢各种宝石的艺术品,可是也不拒绝这样珍贵的金属。但是他只带着一个口袋,口袋至多只能装重量为w的物品。岛上金属有s个种...

【题解】分发饼干

【题目描述】假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;...

第n小质数

【题目描述】蒜头君有一个正整数 n,他想求第 n小的质数。【输入格式】一个不超过 10000的正整数 n。【输出格式】第 n 小的质数。输出...