信息奥赛题解|移动路线
🚀 题目浏览
【题目描述】
桌子上有一个 $m$ 行 $n$ 列的方格矩阵,将每个方格用坐标表示,行坐标从下到上依次递增,列坐标从左至右依次递增,左下角方格的坐标为 $(1,1)$,则右上角方格的坐标为 $(m,n)$。
小明是个调皮的孩子,一天他捉来一只蚂蚁,不小心把蚂蚁的右脚弄伤了,于是蚂蚁只能向上或向右移动。小明把这只蚂蚁放在左下角的方格中,蚂蚁从左下角的方格中移动到右上角的方格中,每步移动一个方格。蚂蚁始终在方格矩阵内移动,请计算出不同的移动路线的数目。
对于 $1$ 行 $1$ 列的方格矩阵,蚂蚁原地移动,移动路线数为 $1$;对于 $1$ 行 $2$ 列(或 $2$ 行 $1$ 列)的方格矩阵,蚂蚁只需一次向右(或向上)移动,移动路线数也为 $1$
对于一个 $2$ 行 $3$ 列的方格矩阵,如下图所示:
$(2,1),(2,2),(2,3)$
$(1,1),(1,2),(1,3)$
蚂蚁共有3种移动路线:
路线1:$(1,1) → (1,2) → (1,3) → (2,3)$
路线2:$(1,1) → (1,2) → (2,2) → (2,3)$
路线3:$(1,1) → (2,1) → (2,2) → (2,3)$
【输入】
输入只有一行,包括两个整数 $m$ 和 $n(0 \lt m+n \le 20)$,代表方格矩阵的行数和列数,$m,n$ 之间用空格隔开。
【输出】
输出只有一行,为不同的移动路线的数目。
【输入样例】
2 3
【输出样例】
7
【原题链接】
http://ybt.ssoier.cn:8088/problem_show.php?pid=1194
☘️ 题解分析
本题是求 到达某点路线方案数 中较为基础的题型,是典型的递推问题。
可以构造一个二维矩阵 a[N][N]
表示总地图,其中 a[i][j]
表示从起点到点 $(i,j)$ 的路线方案数。
由于蚂蚁只能往上或者往右走,因此对于每一个点 a[i][j]
来说,只能从下面的点 a[i-1][j]
或者左边的点 a[i][j-1]
走到,所以到 a[i][j]
的方案数就是从 起点到 a[i-1][j]
和 起点a[i][j-1]
的方案数之和,即递推关系为 a[i][j] = a[i-1][j] + a[i][j-1]
本题数组 a
推荐使用全局变量(全局变量默认初始值为 0),这样在 i = 1
或者 j = 1
时(边界情况下),该方程仍然成立。
- 如起点为 $(1,1)$,想要到点 $(1,2)$ ,只有向右走一种方式,即
a[1][2] = a[1][1] = 1
,但是由于点a[0][2]
在全局变量的情况下,默认值为 0,所以把方程写成a[1][2] = a[1][1] + a[0][2] = 1
也是完全可以的。 - 这样的写法会简化代码,因为不用单独判断最下面一行和最左边一列了。
❗️ 但是在初始化时要注意给 a[1][1]
单独赋值为 1,否则在递推计算时,所有结果均为0。(请思考为什么会这样?)
🧑🏻💻 C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 30;
long long a[N][N];
int main() {
//计算a数组
for (int i = 1; i < N; ++i) {
for (int j = 1; j < N; ++j) {
//注意,a[1][1]的初始值需要单独赋值,否则a数组在该方程下全为0
if (i == 1 && j == 1)
a[i][j] = 1;
else
a[i][j] = a[i - 1][j] + a[i][j - 1];
}
}
int n, m;
cin >> n >> m;
cout << a[n][m] << endl;
return 0;
}