P1176 路径计数2
题目描述
一个N \times NN×N的网格，你一开始在(1,1)(1,1)，即左上角。每次只能移动到下方相邻的格子或者右方相邻的格子，问到达(N,N)(N,N)，即右下角有多少种方法。
但是这个问题太简单了，所以现在有MM个格子上有障碍，即不能走到这MM个格子上。
简单的转移方程方程：
$dp[i][j]=(d[i-1][j]+d[i][j-1])%mod$
由左和上转移而来。
#include<iostream>
#include<cstdio>
#define mod 100003 using namespace std; int d[][],n,m; int main()
{
scanf("%d%d",&n,&m);
for(int x,y,i=;i<=m;i++){
scanf("%d%d",&x,&y);
d[x][y]=-;
}
if(d[][]==-||d[n][n]==-) {
printf("");return ;
}
d[][]=;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++){
if(d[i][j]==-){
d[i][j]=;continue;
}
int z=d[i][j-],s=d[i-][j];
d[i][j]+=(z+s)%mod;
} printf("%d",d[n][n]);
return ;
}