老实的说，这该称之为穷举——但搜索不也是把所有可能的情况列出来么？无非用的方法巧妙一点……额，是巧妙的多罢了。传说中有位俊朗的数学家王子，为了得到邻国数学家公主的一片芳心，发动全国之力，每个人验证一个数是否为质数，从而得到了一个相当大的质数，为古巴比伦数学的蓬勃发展作出了不可磨灭的贡献。——这就是穷举。BTW，他的想法和并行计算机如出一辙，也不知道谁从谁哪里得到的灵感。 但是我听说，两个数学家走到一起，下场都是很悲惨的，不是女孩把拖鞋下到锅里就是男孩饿死。但似乎王子和公主们不用担心这些…… 扯远了。这道题本来想写华丽的bfs……但是写的太华丽了，调试到最后连自己都不知道在写什么。题意是这样的，有9个时钟（A到I），每个时钟只有4档可以拨，12点，3点，6点，9点。有9种操作，每种操作把其中的某几个时钟顺时针拨一档。 Move Affected clocks 1 ABDE 2 ABC 3 BCEF 4 ADG 5 BDEFH 6 CFI 7 DEGH 8 GHI 9 EFHI 那么，给出一个时钟的排列法，如 9 9 126 6 66 3 6 求，最小需要几步，把所有时钟都挑到12点？ 这是一个非常好的bfs和dfs练习题，但是也相当的难写。在看了某牛人的dfs代码之后，我发现自己比看过之前懂的更少。胡Core也教导我们，要以艰苦朴素为荣。综上所述，我采用了穷举的方法。 但是这也是有前提的。第一，每一个时钟都只有四种状态。换句话说，每种操作也是四种状态，进行0，1，2，3次。第二，4的9次方不大…… /*ID: Crux.DPROG: clocksLANG: 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;}

评论