14035 - 走迷宫 Ⅱ

有一个 n 行 m 列的迷宫，行号从 1 到 n ，列号从 1 到 m 。你需要从左上角 (1,1) 出发，到达右下角 (n,m)。

在移动过程中，每次只能选择 向下移动一格（行号 + 1，列号不变）或 向右移动一格（列号 + 1，行号不变）。不能向左或向上移动。

此外，迷宫中有 k 个障碍物网格，你不能经过或停留在这些网格上。保证起点 (1,1) 和终点 (n,m) 不是障碍物。

请你计算从起点到终点的不同移动方案总数。两种方案如果存在某一步，一个方案选择向下而另一个选择向右，则视为不同方案。

第一行包含三个整数 n, m, k ，用空格隔开：

• n ：迷宫的行数
• m ：迷宫的列数
• k ：障碍物的数量 接下来 k 行，每行包含两个整数 ( x, y )，表示一个障碍物所在的行号和列号。

输出一个整数，表示从起点到终点的不同路径总数。

样例说明

一个 3 \times 3 的迷宫，障碍物在中心 (2,2)。从 (1,1) 到 (3,3) 只能向右和向下，不经过 (2,2) 的路径有两条：

1. 右 → 下 → 下 → 右
2. 下 → 下 → 右 → 右

因此输出 2。

数据范围与约定

• 1 \le n, m
• n + m \le 32
• 0 \le k \le n \times m （但保证起点和终点不是障碍物）
• 障碍物坐标均在合法范围内。