当前位置:网站首页>repeat_ P1002 [NOIP2002 popularization group] cross the river pawn_ dp

repeat_ P1002 [NOIP2002 popularization group] cross the river pawn_ dp

2022-07-04 20:06:00 This question AC sleep again

repeat_P1002 [NOIP2002 Popularization group ] River crossing pawn _dp

//
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int dx[]={ 0,1,1,-1,-1,2,2,-2,-2 };
const int dy[]={ 0,2,-2,2,-2,1,-1,1,-1 };
const int N=22;
bool used[N][N];
LL dp[N][N];
int n,m,x,y;

void init()
{
    memset( used,0,sizeof( used ) );
    memset( dp,0,sizeof( dp ) );
    int i,j,tx,ty;
    for( i=0;i<9;i++ )
    {
        tx=x+dx[i]; ty=y+dy[i];
        if( tx>=0 && tx<=n && ty>=0 && ty<=m ) used[tx][ty]=1;
    }
    for( i=0;i<=n;i++ )             // =
    {
        if( used[i][0] ) break;     //
        dp[i][0]=1;
    }
    for( j=0;j<=m;j++ )             // =
    {
        if( used[0][j] ) break;     //
        dp[0][j]=1;
    }
}

int main()
{
    int i,j;
    while( cin>>n>>m>>x>>y )
    {
        init();
        for( i=1;i<=n;i++ )
            for( j=1;j<=m;j++ )
                if( used[i][j]==0 )
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
        cout<<dp[n][m]<<endl;
    }
    return 0;
}

原网站

版权声明
本文为[This question AC sleep again]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/185/202207041714264021.html