马拦过河卒

- 日理万妓 2022-07-11 08:51 180阅读 0赞

马拦过河卒  
描述 Description  
　　棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。  
　　棋盘用坐标表示，A点(0, 0)、B点(n, m)(n, m为不超过20的整数)，同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。  
　　  
输入格式 Input Format  
一行四个数据，分别表示B点坐标和马的坐标。  
输出格式 Output Format  
一个数据，表示所有的路径条数。  
样例输入 Sample Input

6 6 3 3

样例输出 Sample Output

来源 Source  
Noip2002普及组第4题

用f\[i,j\]来表示从(0,0)到(i,j)这个点的路径数量。由于卒只能向下或向右走，因此他上一步只有可能在(i-1,j)或者(i,j-1)处，所以到这点的路径数量便是到这两点的路径数量之和。  
同时如果卒在第一行或者第一列时，只有一个方向。  
用map(i,j)来表示这个点是否能走，然后初始化，去掉所有马占的点(马所在的地方也要去掉)。还要把原点去掉，因为原点到原点的路径是唯一而且没有点能到原点了。

#include<iostream>
    
    using namespace std;
    
    bool map[21][21]={
       0};
    long long f[21][21]={
       0};
    int xx[3]={
       0,0,1};
    int yy[3]={
       0,-1,0};
    
    int max(int a,int b);
    void change(int a,int b);
    
    int main()
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        for (int i=0;i<=x1;++i)
         for (int j=0;j<=y1;++j)
         {
            map[i][j]=1;
         }
        change(x2,y2);
        int i=0,j=0;
        f[0][0]=1;
        for (i=1;i<=x1;i++)
        {
            if (map[i][0])
             f[i][0]=f[i-1][0];
        }
        for (j=1;j<=y1;++j)
        {
            if (map[0][j])
            {
                f[0][j]=f[0][j-1];
            }
        }
        for (i=1;i<=x1;i++)
         for (j=1;j<=y1;j++)
         {
            if (map[i][j])
            f[i][j]=f[i-1][j]+f[i][j-1];
         }
        cout<<f[x1][y1];
    }
    
    int max(int a,int b)
    {
        return a>b?a:b;
    }
    
    void change(int a,int b)
    {
        map[a][b]=0;
        map[a+2][b+1]=0;map[a+2][b-1]=0;
        map[a+1][b+2]=0;map[a+1][b-2]=0;
        map[a-2][b-1]=0;map[a-2][b+1]=0;
        map[a-1][b-2]=0;map[a-1][b+2]=0;
    }