路径计数2
题目描述
一个 的网格，你一开始在
，即左上角。每次只能移动到下方相邻的格子或者右方相邻的格子，问到达
，即右下角有多少种方法。
但是这个问题太简单了，所以现在有 个格子上有障碍，即不能走到这
个格子上。
输入格式
输入文件第 行包含两个非负整数
，表示了网格的边长与障碍数。
接下来 行，每行两个不大于
的正整数
。表示坐标
上有障碍不能通过，且有
，且
至少有一个大于
，并请注意障碍坐标有可能相同。
输出格式
一个非负整数，为答案 后的结果。
样例 #1
样例输入 #1
3 1
3 1样例输出 #1
5提示
对于 的数据，有
；
对于 的数据，有
；
对于 的数据，有
；
对于 的数据，有
。
#include<iostream>
#include<cstdio>
using namespace std;
int f[1001][1001];
int n,m;
int main() {
cin>>n>>m;
for(int i=1; i<=m; i++) {
int a,b;
cin>>a>>b;
f[a][b]=-1;
}
f[1][1]=1;
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
if(f[i][j]!=-1) {
f[i][j]=max(max(f[i][j-1],f[i][j]),max(f[i-1][j],f[i-1][j]+f[i][j-1]));
}
f[i][j]%=100003;
}
}
cout<<f[n][n];
return 0;
}