0203-A New Plan of Aizu Ski Resort

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0203&lang=jp

動的計画法。
上からの進入と左右からの進入の場合わけが面倒。

int x,y,M[50][50],D[50][50],i,j,r;
main(){
        for(;;){
                scanf("%d%d",&x,&y);
                if(x==0)exit(0);
                for(i=0;i<289;i++) {M[i%17][i/17]=1;D[i%17][i/17]=0;}
                for(i=0;i<y;i++)
                        for(j=0;j<x;j++)
                                scanf("%d",&M[j+1][i]);
                for(j=1;j<=x;j++){if(M[j][y-1]!=1)D[j][y-1]=1;D[j][y]=1;}
                for(j=y-2;j>=0;j--){
                        for(i=1;i<=x;i++){
                                if(M[i][j]==0) {
                                        D[i][j]=D[i][j+1];
                                        if(M[i+1][j+1]!=2) D[i][j]+=D[i+1][j+1];
                                        if(M[i-1][j+1]!=2) D[i][j]+=D[i-1][j+1];
                                }
                                if(M[i][j]==2) D[i][j]=D[i][j+2];
                        }
                }
                r=0;
                for(i=1;i<=x;i++){
                        r+=D[i][0];
                }
                printf("%d\n",r);
        }
}