加载中...

信息奥赛题解|移动路线


信息奥赛题解|移动路线


🚀 题目浏览

【题目描述】

桌子上有一个 $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;
}

文章作者: Rickyの水果摊
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Rickyの水果摊 !
  目录