老实的说，这该称之为穷举——但搜索不也是把所有可能的情况列出来么？无非用的方法巧妙一点……额，是巧妙的多罢了。传说中有位俊朗的数学家王子，为了得到邻国数学家公主的一片芳心，发动全国之力，每个人验证一个数是否为质数，从而得到了一个相当大的质数，为古巴比伦数学的蓬勃发展作出了不可磨灭的贡献。——这就是穷举。BTW，他的想法和并行计算机如出一辙，也不知道谁从谁哪里得到的灵感。

但是我听说，两个数学家走到一起，下场都是很悲惨的，不是女孩把拖鞋下到锅里就是男孩饿死。但似乎王子和公主们不用担心这些……

扯远了。这道题本来想写华丽的bfs……但是写的太华丽了，调试到最后连自己都不知道在写什么。题意是这样的，有9个时钟（A到I），每个时钟只有4档可以拨，12点，3点，6点，9点。有9种操作，每种操作把其中的某几个时钟顺时针拨一档。

那么，给出一个时钟的排列法，如

9 9 12
6 6 6
6 3 6

求，最小需要几步，把所有时钟都挑到12点？

这是一个非常好的bfs和dfs练习题，但是也相当的难写。在看了某牛人的dfs代码之后，我发现自己比看过之前懂的更少。胡Core也教导我们，要以艰苦朴素为荣。综上所述，我采用了穷举的方法。

但是这也是有前提的。第一，每一个时钟都只有四种状态。换句话说，每种操作也是四种状态，进行0，1，2，3次。第二，4的9次方不大……

/*
ID: Crux.D
PROG: clocks
LANG: C++
*/

#include <cstdio>
#include <string>
#include <cstdlib>

const int L = 10000;

FILE * fin = fopen ( "clocks.in", "r" );
FILE * fout = fopen ( "clocks.out", "w" );

int x[9];

int c[9][9] = {
{ 1, 1, 0, 1, 1, 0, 0, 0, 0 },
{ 1, 1, 1, 0, 0, 0, 0, 0, 0 },
{ 0, 1, 1, 0, 1, 1, 0, 0, 0 },
{ 1, 0, 0, 1, 0, 0, 1, 0, 0 },
{ 0, 1, 0, 1, 1, 1, 0, 1, 0 },
{ 0, 0, 1, 0, 0, 1, 0, 0, 1 },
{ 0, 0, 0, 1, 1, 0, 1, 1, 0 },
{ 0, 0, 0, 0, 0, 0, 1, 1, 1 },
{ 0, 0, 0, 0, 1, 1, 0, 1, 1 }
}, a[9];

bool res ()
{
    int i;
    int r[9] =
    {
        0, 0, 0, 1, 1, 0, 0, 1, 1
    };
    for ( i = 0; i < 9; i ++ )
    {
        if ( x[i] != r[i] )
        {
            return false;
        }
    }
    return true;
}

bool check ()
{
    int i, k, t[9];
    memcpy ( t, a, sizeof ( t ) );
    for ( i = 0; i < 9; i ++ )
    {
        for ( k = 0; k < 9; k ++ )
        {
            t[k] += c[i][k] * x[i];
        }
    }
    /*
    if ( res () )
    {
        for ( i = 0; i < 9; i ++ )
        {
            printf ( "%d ", t[i] );
        }
        printf ( "\n" );
    }
    */
    for ( i = 0; i < 9; i ++ )
    {
        if ( t[i] % 4 != 0 )
        {
            return false;
        }
    }
    return true;
}

void print ()
{
    int i, k, ct = 0;
    for ( i = 0; i < 9; i ++ )
    {
        for ( k = 0; k < x[i]; k ++ )
        {
            if ( ct ++ )
            {
                fprintf ( fout, " " );
            }
            fprintf ( fout, "%d", i + 1 );
        }
    }
    fprintf ( fout, "\n" );
}

void init ()
{
    int i, t;
    for ( i = 0; i < 9; i ++ )
    {
        fscanf ( fin, "%d", &t );
        a[i] = t / 3 % 4;
    }
}

void enu ()
{
    for ( x[0] = 0; x[0] < 4; x[0] ++ )
    {
        for ( x[1] = 0; x[1] < 4; x[1] ++ )
        {
            for ( x[2] = 0; x[2] < 4; x[2] ++ )
            {
                for ( x[3] = 0; x[3] < 4; x[3] ++ )
                {
                    for ( x[4] = 0; x[4] < 4; x[4] ++ )
                    {
                        for ( x[5] = 0; x[5] < 4; x[5] ++ )
                        {
                            for ( x[6] = 0; x[6] < 4; x[6] ++ )
                            {
                                for ( x[7] = 0; x[7] < 4; x[7] ++ )
                                {
                                    for ( x[8] = 0; x[8] < 4; x[8] ++ )
                                    {
                                        if ( check () )
                                        {
                                            print ();
                                            goto out;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    out:
    return;
}

int main ()
{
    init ();
    enu ();
    return 0;
}

评论