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

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

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

 【题目描述】

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]

注意边界点即可。




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

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

分享给朋友:

相关文章

【题解】零花钱

零花钱(money.cpp) 【问题描述】 商店里有一件玩具,今天你偶然得知:这件玩具在后⾯的n天里每天的定价(价格可能每天都会改 变),你买了这件玩具后可以以当天的价格卖给商店,...

【题解】冒泡排序计数

【题目描述】考虑冒泡排序的一种实现。bubble-sort  (A[],  n)>   round  =  0>   while...

【题解】线段

【题目描述】在一个数轴上有n条线段,现选取其中k条线段使得这k条线段两两没有重合部分,问最大的k为多少?【输入描述】第一行为一个正整数n,下面n行每行2个数字ai,bi,描述每条线段。【输出描述】输出...

【题解】最大平方因子

【题目描述】给定一个整数 n,请找出 n 的最大平方因子。所谓平方因子,就是一个 n 的因子,且是一个完全平方数。最大平方因子就是 n&nb...

【题解】钟神赛车

【题目描述】钟神近来编码劳累,想骑车风光一番,于是找某君骑自行车比赛。已知某君和钟神的每辆自行车的速度,钟神赢一场得50银两银子,输一场赔50银两,平局不挣也不赔。钟神可以随意安排高中低档自行车的出场...

【题解】跳格子

【题目描述】地面上有一排长度为n的格子1-n,每个格子上都有一个数xi,开始时你在位置0,每次你可以向前跳1-2格,然后取走格子上的数,直到跳到位置n+1。取走的数的和就是你的得分,现在你想知道你可能...