首页 > 代码库 > UVALive 6470 Chomp --记忆化搜索

UVALive 6470 Chomp --记忆化搜索

2024-07-12 10:35:23   223人阅读

题意：给一个只有三行的方块阵（横向最多100个），然后p,q,r分别代表第1,2,3层的方格数，两人轮流去掉一个格子，此时这个格子的右上方都会被去掉，面临只剩最左下角的一个格子的状态的人输，问先手能否赢，要赢得话应该取哪个方格。

解法：记忆化搜索，设dp[p][q][r]表示第1,2,3层方格数分别为p,q,r的输赢状态，0为输，1为赢，X[][][],Y[][][]分别表示其该取的方格坐标。每次求dp[p][q][r]时，枚举能达到的状态，如果这些状态的输赢值有一个为输，则此状态一定为赢，返回1，并记录好坐标，如果没有一个为输，则此状态为输。

初始值：

dp[1][0][0] = 0;

dp[1][1][0] = 1,X[1][1][0] = 1,Y[1][1][0] = 2;

dp[2][0][0] = 1,X[2][0][0] = 2,Y[2][0][0] = 1;

注意初始状态一定要最原始化，不要添加诸如只有最底层并且有n个，dp[n][0][0] = 1等的状态，因为不一定要这样取，也可能该行一个一个的取。

记忆化搜索加快速度

代码：

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <cstdlib>#include <algorithm>using namespace std;#define N 1007#define M 33int dp[104][104][104];int X[104][104][104],Y[104][104][104];int kx,ky;void init(){    memset(dp,-1,sizeof(dp));    memset(X,0,sizeof(X));    memset(Y,0,sizeof(Y));    //dp[0][0][0] = 1;    dp[1][0][0] = 0;            //写出最基本的几个即可，不要乱加    dp[1][1][0] = 1,X[1][1][0] = 1,Y[1][1][0] = 2;    //dp[1][1][1] = 1,X[1][1][1] = 2,Y[1][1][1] = 1;    //for(int i=2;i<=100;i++)    dp[2][0][0] = 1,X[2][0][0] = 2,Y[2][0][0] = 1;}int DP(int p,int q,int r){    if(dp[p][q][r] != -1)        return dp[p][q][r];    int i;    for(i=r;i>=1;i--)   //顶层    {        if(DP(p,q,i-1) == 0)        {            X[p][q][r] = i;            Y[p][q][r] = 3;            return dp[p][q][r] = 1;        }    }    for(i=q;i>=1;i--)    //中层    {        if(DP(p,i-1,min(r,i-1)) == 0)        {            X[p][q][r] = i;            Y[p][q][r] = 2;            return dp[p][q][r] = 1;        }    }    for(i=p;i>=2;i--)   //底层，注意>=2而不是1    {        if(DP(i-1,min(q,i-1),min(r,i-1)) == 0)        {            X[p][q][r] = i;            Y[p][q][r] = 1;            return dp[p][q][r] = 1;        }    }    return dp[p][q][r] = 0;}int main(){    int p,q,r,t,cs;    scanf("%d",&t);    init();    while(t--)    {        scanf("%d%d%d%d",&cs,&p,&q,&r);        if(DP(p,q,r))            printf("%d W %d %d\n",cs,X[p][q][r],Y[p][q][r]);        else            printf("%d L\n",cs);    }    return 0;}
View Code


联系
我们