#AT25. Grid 2
Grid 2
[Y] Grid 2(dp_y)
来源: AtCoder Educational DP Contest - Problem Y 原题时限:2 秒 / 内存:1024 MB
题目描述
有一个 行 列的网格。记第 行第 列的格子为 。
网格中有 个格子 是墙,其余格子全部是空地。保证格子 与 是空地。
太郎从格子 出发,每次只能向右或向下移动到相邻的空地,最终到达格子 。
求从 到 的路径数,对 取模。
输入格式
输入由标准输入按以下格式给出:
H W N
r_1 c_1
r_2 c_2
:
r_N c_N
输出格式
输出路径数对 取模的结果。
数据范围
- 所有 两两不同。
- 格子 与 为空地。
样例 1
输入:
3 4 2
2 2
1 4
输出:
3
样例 2
输入:
5 2 2
2 1
4 2
输出:
0
样例 3
输入:
5 5 4
3 1
3 5
1 3
5 3
输出:
24
样例 4
输入:
100000 100000 1
50000 50000
输出:
123445622