NOIP 2002 过河卒(记忆化DFS||DP)

ゞ浴缸里的玫瑰 2022-05-17 11:17 195阅读 0赞

题目描述

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

![pimg1037_1.gif][]

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

输入

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

输出

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

分析：到终点的路径是由之前的点一个一个递推来的，并且每到一个点，是不用管之前的状态是怎么来的，只需要用现在的状态又去不断递推后面的状态，那么其实也就满足了最优子结构，并且无后效性，那么也就想到了用DP来做，dp（i，j）表示从起点到（i，j）这个点的走法有多少种，然后把马本身和马的控制范围的点都打上标记，表明这些点不能走，将dp\[0\]\[0\]赋初值为1，然后DP即可。。。其实这种问题很容易也可以想到用递归来做，但不能常规递归，因为中间重复计算了很多次，所以要用记忆化搜索。 注意数字较大，用long long 能过。

代码1 记忆化搜索：

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<cctype>
    #include<cstring>
    #include<utility>
    #include<cstdlib>
    #include<iomanip>
    #include<iostream>
    #include<algorithm>
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    using namespace std;
    const int maxn = 27;
    const int inf = 0x3f3f3f3f;
    const double pi=acos(-1.0);
    const double eps = 1e-3;
    int vis[maxn][maxn];
    ll f[maxn][maxn];
    int n,m,x,y;
    
    int read()
    {
        char ch=getchar();int ret=0,f=1;
        while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
        return f*ret;
    }
    
    ll DFS(int x,int y)
    {
        if(f[x][y]) return f[x][y];
        if(x>n||y>m) return 0;
        if(x==n&&y==m) return 1;
        if(vis[x+1][y]==0&&x+1<=n) f[x][y]+=DFS(x+1,y);
        if(vis[x][y+1]==0&&y+1<=m) f[x][y]+=DFS(x,y+1);
        return f[x][y];
    }
    
    int main()
    {
        n=read(),m=read(),x=read(),y=read();
        Clear(f);
        Clear(vis);
        vis[x][y]=1;
        vis[x-1][y-2]=1,vis[x-2][y-1]=1,vis[x-2][y+1]=1,vis[x-1][y+2]=1;
        vis[x+1][y+2]=1,vis[x+2][y+1]=1,vis[x+2][y-1]=1,vis[x+1][y-2]=1;
        cout<<DFS(0,0)<<endl;
        return 0;
    }

代码2 dp：

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<cctype>
    #include<cstring>
    #include<utility>
    #include<cstdlib>
    #include<iomanip>
    #include<iostream>
    #include<algorithm>
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    using namespace std;
    const int maxn = 27;
    const int inf = 0x3f3f3f3f;
    const double pi=acos(-1.0);
    const double eps = 1e-3;
    int vis[maxn][maxn];
    ll dp[maxn][maxn];//表示从起点走到(i,j)处有几条路径
    int dir[][2]={
       {0,0},{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}};
    int n,m,x,y;
    
    int read()
    {
        char ch=getchar();int ret=0,f=1;
        while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
        return f*ret;
    }
    
    void mark()
    {
        for(int i=0;i<9;i++)
        {
            if(x+dir[i][0]>=0&&x+dir[i][0]<=n&&y+dir[i][1]>=0&&y+dir[i][1]<=m)
                vis[x+dir[i][0]][y+dir[i][1]]=1;
        }
    }
    
    void slove()
    {
        dp[0][0]=1;
        for(int i=0;i<=n;i++)
        {
            for(int j=0;j<=m;j++)
            {
                if(vis[i][j]) continue;
                if(i) dp[i][j]+=dp[i-1][j];//如果不在第一行就要加上上面一行递推过来的路径数
                if(j) dp[i][j]+=dp[i][j-1];//如果不在第一列就要加上上面一行递推过来的路径数
            }
        }
        /**
        可以打出路径便于理解
        for(int i=0;i<=n;i++)
        {
            for(int j=0;j<=m;j++)
            {
                printf("%d ",dp[i][j]);
            }
            printf("\n");
        }*/
        printf("%lld\n",dp[n][m]);
    }
    
    int main()
    {
        n=read(),m=read(),x=read(),y=read();
        Clear(dp);
        Clear(vis);
        mark();
        slove();
        return 0;
    }

[pimg1037_1.gif]: /images/20220517/f0baa482ea1b4a1c86f3a4e1186a9501.png