走出迷宫的方法数2

ID: 4310

传统题

1000ms

128MiB

难度: 3

上传者:

题目描述

有一个 n * m 的矩阵迷宫，其中有 k 个位置有障碍，障碍位置无法通过，如果从 (1, 1) 点出发，只能向下或者向右行走，请问走到 (n, m) 点有多少种不同的方法。

第 1 行有 3 个整数 n、m、k（2 <= n, m <= 1000, 1 <= k <= 10000）

接下来 k 行，每行 2 个整数 $x_i、y_i$，表示障碍物的位置，保证障碍物不会在起点或终点

输出 1 个整数，表示总方法数

（数据类型用 int，默认发生溢出）

3 3 1
2 2

数据约束

对 50% 的数据：2 <= n, m <= 100, 1 <= k <= 100

对 100% 的数据：2 <= n, m <= 1000, 1 <= k <= 10000

在以下作业中: