JOI 2006 予選 F 通学経路

問題

見た感じ

格子点上で進んでいくという問題で遠回りしないので、以下の漸化式を計算すればよさそう。

dp[i][j]=(1,1)から格子点(i,j)までの工事現場を通らない経路数\\
工事現場を(x,y)とするとdp[x][y]=0でfix\\
dp[i][j]=dp[i-1][j]+dp[i][j-1]\\
dp[1][1]=1

解法

上の漸化式を計算するときに、マンハッタン距離順で計算していけば2重ループで書ける。

ソースコード

const int N_MAX=23;
ll dp[N_MAX][N_MAX];
int n,a,b;

ll solve(){
    dp[1][1]=1;
    rep1(i,a)dp[i][0]=0;//rep1(i,a)=for(int i=1;i<=a;i++)
    rep1(i,b)dp[0][i]=0;
    for(int i=3;i<=a+b;i++){
        for(int j=1;j<i&&j<=a;j++){
            if(dp[j][i-j]<0){
                dp[j][i-j]=dp[j-1][i-j]+dp[j][i-j-1];
            }
        }
    }
    return dp[a][b];
}

int main(){
    int i,x,y;
    //入力
    memset(dp,-1,sizeof(dp));
    cin>>a>>b;
    cin>>n;
    rep(i,n){
        cin>>x>>y;
        dp[x][y]=0;
    }
    //処理
    ll ans=solve();
    //出力
    puts(ans);
}