【题解】上学线路（2019青岛市程序设计比赛）
【题目描述】
小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]
注意边界点即可。
扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。