1314:[例3.6]过河卒(Noip2002)

传送门:     [题目描述]

棋盘上A点有一个过河卒,需要走到目标B点。卒行走的规则:可以向下、或者向右。同时在棋盘上的某一点有一个对方的马(如C点),该马所在的点和所有跳跃一步可达的点称为对方马的控制点,如图3-1中的C点和P1,……,P8,卒不能通过对方马的控制点。棋盘用坐标表示,A点(0,0)、B点(n, m) (n,m为不超过20的整数),同样马的位置坐标是需要给出的,C≠A且C≠B。现在要求你计算出卒从A点能够到达B点的路径的条数。

[输入]

给出n、m和C点的坐标。

[输出]

从A点能够到达B点的路径的条数。

[输入样例]
8 6 0 4
[输出样例]
1617


#includeiostream
#includecstring
using namespace std;
#define N 25
int l[]={1,1,-1,-1,2,2,-2,-2};
int o[]={2,-2,2,-2,1,-1,1,-1};
string dp[N],k[N];
int n,m,x1,y1;
bool no[N][N];
string g(string a,string b)
{
    string ans;
    int as[255]={0},bs[255]={0},cs[255]={0},len;
    memset(as,0,sizeof(as));
    memset(bs,0,sizeof(bs));
    for(int i=0;ia.size();i++)if(a[a.size()-i-1]='0'a[a.size()-i-1]='9')as[i]=a[a.size()-i-1]-'0';
    for(int i=0;ib.size();i++)if(b[b.size()-i-1]='0'b[b.size()-i-1]='9')bs[i]=b[b.size()-i-1]-'0';
    len=max(a.size(),b.size());
    for(int i=0;ilen;i++)
        cs[i]=as[i]+bs[i];
    for(int i=0;ilen;i++)
        if(cs[i]9)
        {
            cs[i+1]++;
            cs[i]-=10;
            if(i==len-1)len++;
        }
    while(cs[len]==0)len--;
    for(int i=0;i=len;i++)
    {
        char s=(cs[i]+'0');
        ans=s+ans;
    }
    // coutansendl;
    return ans;
}
int main()
{
    // string a,b;
    // cinab;
    // coutg(a,b)endl;

    cinnmx1y1;
    memset(no,true,sizeof(no));
    dp[0]="1";

    no[x1][y1]=false;
    for(int i=0;i8;i++)no[x1+l[i]][y1+o[i]]=false;

    for(int i=1;i=m;i++)
    {
        dp[i]=dp[i-1];
        if(no[0][i]==false)dp[i]="0";
    }

    k[0]="1";
    for(int i=1;i=n;i++)
    {
        k[i]=k[i-1];
        if(no[i][0]==false)k[i]="0";
    }

    for(int i=1;i=n;i++)
    {
        for(int j=1;j=m;j++)
        {
            if(j==1)
            {
                dp[j]=g(dp[j],k[i]);
            }
            else dp[j]=g(dp[j],dp[j-1]);
            if(no[i][j]==false)dp[j]="0";
            // coutdp[j]" ";
        }
        // for(int j=1;j=m;j++)
        //     coutdp[j]" ";
        // coutendl;
    }
    coutdp[m]endl;
}

 

转载于:https://www.cnblogs.com/jzxnl/p/11106399.html

最新回复(0)
/jishuqOTnz_2F9a4A_2FKLNkzcDmxLPEeKhICFpiAJam0_2FQ_3D_3D8