路径统计

题目描述

有一个 $n$ 行 $m$ 列的方格地图。

小明从左上角 $(1,1)$ 出发，想走到右下角 $(n,m)$。

每一步只能向两个方向移动：

向下：从 (x,y) 走到 (x+1,y)
向右：从 (x,y) 走到 (x,y+1)

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

输入格式

输入一行，包含两个整数 $n,m$。

输出格式

输出一个整数，表示不同路径的数量。

数据范围

1 ≤ n ≤ 9
1 ≤ m ≤ 9

样例输入 1

2 2

样例输出 1

2

样例解释 1

从 $(1,1)$ 到 $(2,2)$ 有两种走法：

右 → 下
下 → 右

样例输入 2

3 3

样例输出 2

6

提示

可以使用深度优先搜索，从起点开始枚举所有可能的路线。

每次尝试：

向下走
向右走

当走到终点时，答案加一。