2296. 右脚扭伤的机械螃蟹“小八”
1000ms
256MB
简单
递推算法
题目描述
一个 $n$ 行 $m$ 列的方格网格，每个方格的坐标用 $(x, y)$ 表示，其中左上角为 $(1,1)$，右下角为 $(n,m)$。
有一只右脚受伤的机械螃蟹，它只能**向下**或**向右**移动。它从左上角 $(1,1)$ 出发，目标是移动到右下角 $(n,m)$。每次移动只能前进一个方格，且螃蟹必须始终在网格内部移动。
请你计算螃蟹从起点到终点共有多少种不同的移动路线。
**注意：**
- 对于 $1$ 行 $1$ 列的网格，螃蟹不需要移动，路线数为 $1$。
- 对于 $2$ 行 $3$ 列的网格，螃蟹共有 $3$ 种移动路线：
- 路线 1：$(1,1) \to (1,2) \to (1,3) \to (2,3)$
- 路线 2：$(1,1) \to (1,2) \to (2,2) \to (2,3)$
- 路线 3：$(1,1) \to (2,1) \to (2,2) \to (2,3)$
输入格式
一行，包含两个正整数 $n$ 和 $m$ ($0 \lt n, m \le 20$)，代表方格矩阵的行数和列数。
输出格式
一行，输出一个整数，表示不同的移动路线总数。
样例 1
输入 (Input)
2 3
输出 (Output)
3
- 对于所有数据：$0 \lt n, m \le 20$。
- **数学提示**：从 $(1,1)$ 到 $(n,m)$，一共需要向下走 $n-1$ 步，向右走 $m-1$ 步。总步数为 $n+m-2$。不同的路线数实际上是组合数：
$$\binom{n+m-2}{n-1}$$
- **数据溢出提示**：当 $n = 20, m = 20$ 时，总路线数最大为 $\binom{38}{19} = 35,345,263,800$，该值已经超出了 32 位有符号整型（`int`）的最大范围（约 $2 \times 10^9$）。**请务必使用 64 位整型（C++ 中的 `long long`）进行存储与计算**，否则会导致计算结果发生整除或加法溢出。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功