网格路径数量

题目描述

有一个 (n) 行 (m) 列的网格，左上角坐标为 ((1,1))，右下角坐标为 ((n,m))。

小明从左上角 ((1,1)) 出发，想走到右下角 ((n,m))。每一步只能向下或向右移动一格。

也就是说，若当前在位置 ((x,y))，下一步只能移动到：

• ((x+1,y))，即向下移动；
• ((x,y+1))，即向右移动。

请你计算从 ((1,1)) 走到 ((n,m)) 一共有多少条不同的路径。

输入格式

输入一行，包含两个整数 (n) 和 (m)，分别表示网格的行数和列数。

输出格式

输出一个整数，表示从左上角走到右下角的不同路径数量。

数据范围

对于所有测试数据，满足：

$1 \le n,m \le 9$

样例输入 1

2 2

样例输出 1

2

样例解释 1

从 ((1,1)) 到 ((2,2)) 有以下两条路径：

向下 -> 向右
向右 -> 向下

所以答案为 (2)。

样例输入 2

3 3

样例输出 2

6

样例解释 2

从 ((1,1)) 到 ((3,3))，一共需要走 (2) 步向下和 (2) 步向右。

不同的移动顺序共有 (6) 种，因此答案为 (6)。

提示

可以使用深度优先搜索 DFS 从起点开始枚举所有路径。

每次递归时，尝试向下或向右移动。如果到达终点，则路径数量加 (1)。