【题目描述】

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

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

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

【输入格式】

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

【输出格式】

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

【输入输出样例】

【数据规模和约定】

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]

注意边界点即可。