P1002过河卒

传送

因为卒每到一个点上，就有两种情况。1.从左边过来。2.从上面过来。我们设f[i][j]为卒到[i][j]这个点的方案数，那么方程就是f[i][j]=f[i-1][j]+f[i][j-1]，边界状态为f[i][0]=0,f[0][i]=0。哦，等等好像有什么不对的，如果马的控制点在边界上怎么办？那就从控制点开始，后面的f[i][0](或f[0][i])=0呗。but马有8个控制点，所以就要讨论8种情况。马的控制点为[x][y],[x-2][y+1],[x-2][y-1],[x-1][y-2],[x-1][y+2],[x+1][y-2],[x+1][y+2],[x+2][y-1],[x+2][y+1]。知道这些后，就可以写程序（暴力打表）了

打表如下：

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
long long x,y,n,m,f[21][21];
int main()
{
     cin>>n>>m>>x>>y;
     for(int i=0;i<=n;i++)
     {  
         if(y==0)
         {if(i<x)
           f[i][0]=1;
         }
         if(y!=0)
          f[i][0]=1;
     }
     for(int i=0;i<=m;i++)
     {  
       if(x==0)//滤掉马在边界上
       {if(i<y)
          f[0][i]=1;
         } 
        if(x!=0)
        f[0][i]=1;
     }
      if(x-1==0)
      { if(y-2>0)
        {for(int i=y-2;i<=m;i++)
        f[0][i]=0;
        }
        else
        {for(int i=y+2;i<=m;i++)
          f[0][i]=0;
        }
      }
      if(x-2==0)
      {if(y-1>0)//分情况讨论
       {for(int i=y-1;i<=n;i++)
        f[i][0]=0;
        }
        else 
        {for(int i=y-1;i<=n;i++)
        f[i][0]=0;
        }      
      }
      if(y-1==0)
      {if(x-2>0)
       {for(int i=x-2;i<=n;i++)
         f[i][0]=0;
        }
        else 
        {for(int i=x+2;i<=n;i++)
        f[i][0]=0;
        }
      }
      if(y-2==0)
      {if(x-1>0)
        {for(int i=x-1;i<=n;i++)
        f[i][0]=0;
        }
        else
        {for(int i=x+1;i<=n;i++)
        f[i][0]=0;
        }
      }//十分恶心的初始化
    for(int i=1;i<=n;i++)//核心程序开始
    {
         for(int j=1;j<=m;j++)
         {  if((i==x&&j==y)||(i==x-2&&j==y-1)||
(i==x-2&&j==y+1)||(i==x-1&&j==y-2)||(i==x-1&&j==y+2)
||(i==x+1&&j==y-2)||(i==x+1&&j==y+2)||(i==x+2&&j==y-1)||
(i==x+2&&j==y+1))//暴力打表(其实可以用bool标记一下，但我不会)
               continue;
               f[i][j]=f[i-1][j]+f[i][j-1];
        }
     }
     cout<<f[n][m];
}//总之方程很好想，初始化很恶心