STEP BY STEP

POJ百练 - 2814:拨钟问题

发表于 分类于 ， 阅读次数： Valine：
本文字数： 2.4k 阅读时长 ≈ 2 分钟

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

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

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

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#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重循环,多省心…真不该歧视某种方法的…

相关文章