POJ百练 - 2814:拨钟问题

链接: http://poj.grids.cn/practice/2814

个题目可以枚举或者直接暴力。但是,这之前必须弄明白答案的解空间。。。也就是解可能的情况。。。很简单,一共有9种移动方案。也很了然的知道对于某种方案使用N次的效果等同于N%4的效果,也就是说某种方案只可能使用0,1,2,3次。。。一共有9种方案,那么一共就只有4^9种可能的解。。。这么小的解空间,无论用什么方法都不会超时了。。。暴力可以才用9重循环,或者深搜,当时觉得写9重循环是件很糗的事情,就果断深搜了。。。
如果这题才用枚举的方法的话,思考方式还是那样先确定假设解的部分情况,通过已经知道的规则确定解的其它情况,然后求出这个解,判断这个解是否满足题目要求。。。比如,我们可以枚举1,2,3号方案的情况,根据规则确定其它方案的使用情况,求出所有方案的使用情况后,判断假设的解是否满足要求就可以了...

我才用的是dfs+剪枝,这个题目其实题意或者说答案有误,因为答案是搜索找到第一个解,而不是所谓的最短序列的解,当然如果数据使得2者都是一样的话,那么题意就无误了...我的代码是假设找到的第一个就是最短序列的,这种情况下才能使用剪枝,因为找到一个解后就不需要继续找了...


代码如下:
#include <stdio.h>
int nMinTimes;
int nPath[40];
bool bFind = false;
char* szMoves[10] =
{
    NULL,
    "ABDE",
    "ABC",
    "BCEF",
    "ADG",
    "BDEFH",
    "CFI",
    "DEGH",
    "GHI",
    "EFHI"
};
bool IsPosOK(int* nPos)
{
    for (int i = 0; i < 9; ++i)
    {
        if (nPos[i])
        {
            return false;
        }
    }
    return true;
}
void Move(int nChoose, int nTimes, int* nPos)
{
    if (nTimes > 0)
    {
        char* pszStr = szMoves[nChoose];
        while (*pszStr)
        {
            nPos[*pszStr - 'A'] = (nPos[*pszStr - 'A'] + nTimes) % 4;
            ++pszStr;
        }
    }
}
void MoveBack(int nChoose, int nTimes, int* nPos)
{
    if (nTimes > 0)
    {
        char* pszStr = szMoves[nChoose];
        while (*pszStr)
        {
            nPos[*pszStr - 'A'] = (nPos[*pszStr - 'A'] - nTimes + 4) % 4;
            ++pszStr;
        }
    }
}
void Cal(int nChoose, int* nPos, int* nUsed, int nUsedTimes)
{
    if (nChoose == 10)
    {
        if (IsPosOK(nPos) && !bFind)
        {
            nMinTimes = nUsedTimes;
            for (int i = 0; i < nMinTimes; ++i)
            {
                nPath[i] = nUsed[i];
            }
            bFind = true;
        }
        return;
    }
    for (int i = 0; i <= 3; ++i)
    {
        Move(nChoose, i, nPos);
        for (int j = 0; j < i; ++j)//放入i次的nChoose
        {
            nUsed[nUsedTimes + j] = nChoose;
        }
        if (!bFind)
        {
            Cal(nChoose + 1, nPos, nUsed, nUsedTimes + i);
        }
        MoveBack(nChoose, i, nPos);
    }
}
int main()
{
    int nPos[9];
    int nUsed[40];
    for (int i = 0; i < 9; ++i)
    {
        scanf("%d", &nPos[i]);
    }
    Cal(1, nPos, nUsed, 0);
    for (int i = 0; i < nMinTimes; ++i)
    {
        printf("%d", nPath[i]);
        if (i != nMinTimes - 1)
        {
            putchar(' ');
        }
        else
        {
            putchar('\n');
        }
    }
    
    return 0;
}

这道题其实我wa了近10次,原因就是Move和MoveBack写错了,没有移动nTimes次,而前面一直写成了1,昨晚wa得实在无语了...今天晚上检查才突然发现的...
这半个多月做了60道题了,都没有改动这低级的bug习惯...实在无语...递归,回溯,剪枝都写上了...唉...实在无语...还不如直接9重循环,多省心...真不该歧视某种方法的...

posted on 2011-11-28 19:55 yx 阅读(3931) 评论(0)  编辑 收藏 引用 所属分类: 搜索模拟


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

公告

常用链接

留言簿(3)

随笔分类

随笔档案

me

好友

同学

网友

搜索

最新评论

阅读排行榜

评论排行榜