题目描述

一个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
     
      #include
      
       #define mod 100003using namespace std;int d[1005][1005],n,m;int main(){    scanf("%d%d",&n,&m);    for(int x,y,i=1;i<=m;i++){        scanf("%d%d",&x,&y);        d[x][y]=-1;    }    if(d[1][1]==-1||d[n][n]==-1) {        printf("0");return 0;    }    d[1][1]=1;    for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++){            if(d[i][j]==-1){                d[i][j]=0;continue;                    }            int z=d[i][j-1],s=d[i-1][j];            d[i][j]+=(z+s)%mod;        }            printf("%d",d[n][n]);    return 0;}