路径计数2

路径计数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;
}