3065: [2002_p4]过河卒

时间限制: 1 Sec  内存限制: 125 MB

提交: 12  解决: 5

[][][][命题人:外部导入][] [TestData]

题目描述

如图，A点有一个过河卒，需要走到目标B点。卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如图中的C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如图中C 点上的马可以控制9个点（图中的P1，P2...P8 和C）。卒不能通过对方马的控制点。

棋盘用坐标表示，A点（0,0）、B点（n,m）（n，m 为不超过20的整数，并由键盘输入），同样马的位置坐标是需要给出的（约定：C<>A，同时C<>B）。现在要求你计算出卒从A点能够到达B点的路径的条数。

 

输入

每个测试文件只包含一组测试数据，每组输入四个整数n，m，x，y。（（n,m）表示B点的坐标，（x,y）表示对方马的坐标）

 

输出

对于每组输入数据，输出一个整数，表示路径的条数。

 

样例输入

6 6 3 2

样例输出

17 解题思路：开始我是直接暴力搜索，但是超时了，然后优化了一下时间复杂度，采用了记忆化搜索，开一个ans二维数组用于保存每个点到达终点的路径次数，这样当下次搜到这个点时，可以直接得到路径次数。 下面分别贴出两次提交的代码： 第一次超时：

#include
     
      using namespace std; int hi,hj,ei,ej;int cnt;int dir[2][2]={
   {
   0,1},{
   1,0}}; bool check(int a,int b){    if(a>ei||b>ej||(a==hi&&b==hj)||(a==hi-1&&b==hj-2)       ||(a==hi+1&&b==hj-2)||(a==hi-2&&b==hj-1)       ||(a==hi+2&&b==hj-1)||(a==hi+1&&b==hj+2)       ||(a==hi-1&&b==hj+2)||(a==hi+2&&b==hj+1)       ||(a==hi-2&&b==hj+1))return false;    else return true;} void dfs(int x,int y){    if(x==ei&&y==ej){cnt++;return;}    for(int i=0;i<2;++i)    {        x+=dir[i][0];        y+=dir[i][1];        if(check(x,y))        {            dfs(x,y);        }        x-=dir[i][0];        y-=dir[i][1];    }} int main(){    while(cin>>ei>>ej>>hi>>hj)    {        cnt=0;        dfs(0,0);        cout<
      
       <
      
     

第二次AC：

#include 
      
       #include 
       
        using namespace std; int hi,hj,ei,ej;int cnt;int dir[2][2]={
    {
    0,1},{
    1,0}};long long ans[21][21];//这里要用longlong，因为当格子数很多的时候，路径会超多的，用int会wabool check(int a,int b){    if(a>ei||b>ej||(a==hi&&b==hj)||(a==hi-1&&b==hj-2)       ||(a==hi+1&&b==hj-2)||(a==hi-2&&b==hj-1)       ||(a==hi+2&&b==hj-1)||(a==hi+1&&b==hj+2)       ||(a==hi-1&&b==hj+2)||(a==hi+2&&b==hj+1)       ||(a==hi-2&&b==hj+1))return false;    else return true;} long long dfs(int x,int y){    if(ans[x][y]!=-1)return ans[x][y];    if(x==ei&&y==ej)    {        cnt++;        return 1;    }    long long res=0;    for(int i=0;i<2;++i)    {        x+=dir[i][0];        y+=dir[i][1];        if(check(x,y))        {            res+=dfs(x,y);        }        x-=dir[i][0];        y-=dir[i][1];    }    return ans[x][y]=res;//保存每一个点到终点的路径数} int main(){    while(cin>>ei>>ej>>hi>>hj)    {        memset(ans,-1,sizeof ans);        cnt=0;        dfs(0,0);        cout<
        
         <