首页 > 其他 > 详细

UVALive 6470 Chomp --记忆化搜索

时间:2014-07-18 23:37:52      阅读:483      评论:0      收藏:0      [点我收藏+]

题意:给一个只有三行的方块阵(横向最多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等的状态,因为不一定要这样取,也可能该行一个一个的取。

记忆化搜索加快速度

代码:

bubuko.com,布布扣
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define N 1007
#define M 33

int 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

UVALive 6470 Chomp --记忆化搜索,布布扣,bubuko.com

UVALive 6470 Chomp --记忆化搜索

原文:http://www.cnblogs.com/whatbeg/p/3849997.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!