luogu#P1176. 路径计数2
路径计数2
题目描述
一个 的网格,你一开始在 ,即左上角。每次只能移动到下方相邻的格子或者右方相邻的格子,问到达 ,即右下角有多少种方法。
但是这个问题太简单了,所以现在有 个格子上有障碍,即不能走到这 个格子上。
输入格式
输入文件第 行包含两个非负整数 ,表示了网格的边长与障碍数。
接下来 行,每行两个不大于 的正整数 。表示坐标 上有障碍不能通过,且有 ,且 至少有一个大于 ,并请注意障碍坐标有可能相同。
输出格式
一个非负整数,为答案 后的结果。
3 1
3 1
5
提示
对于 的数据,有;
对于 的数据,有;
对于 的数据,有;
对于 的数据,有。