USACO sec1.4 The Clocks

使用したBFSは、それぞれの数字を4で割って、4つの異なる状態を得た:0 1 2 3、判重を実現するために、2ビットで1つの状態を表し、時計全体に2*9=18ビットが必要で、大きくない;
問題解の2つ目のやり方は推理が一般的な解法を得たようだ.

  1 /*

  2 PROG : clocks

  3 LANG : C++

  4 */

  5 

  6 # include <cstdio>

  7 # include <cstring>

  8 # include <queue>

  9 

 10 using namespace std;

 11 

 12 int ss;

 13 char vis[0x3FFFF + 0x1];

 14 int pre[0x3FFFF + 0x1];

 15 int solu[200];

 16 

 17 /*********************************/

 18 const int od[][6] = 

 19 {

 20     {0,1,3,4, -1,0},

 21     {0,1,2,-1,0,0},

 22     {1,2,4,5,-1,0},

 23     {0,3,6,-1,0,0},

 24     {1,3,4,5,7,-1},

 25     {2,5,8,-1,0,0},

 26     {3,4,6,7,-1,0},

 27     {6,7,8,-1,0,0},

 28     {4,5,7,8,-1,0}

 29 };

 30 /*********************************/

 31 

 32 int flip(int s, int id)

 33 {

 34     int i, t, tt;

 35     for (i = 0; od[id][i] != -1; ++i)

 36     {

 37         //printf("\t%d\t", od[id][i]);

 38         t = 2 * od[id][i];

 39         tt = ((((s>>t)&0x3)+1)&0x3);

 40         s &= ~(0x3<<t);

 41         s |= tt<<t;

 42     }

 43     return s;

 44 }

 45 

 46 void bfs(int ss)

 47 {

 48     int x, y, i;

 49     queue <int> Q;

 50     

 51     if (ss == 0x3FFFF) return ;

 52     

 53     memset(vis, 0, sizeof(vis));

 54     while (!Q.empty()) Q.pop();

 55     

 56     vis[ss] = 1;

 57     Q.push(ss);

 58     while (!Q.empty())

 59     {

 60         x = Q.front(); Q.pop();

 61         for (i = 0; i < 9; ++i)

 62         {

 63             y = flip(x, i);

 64         //printf("%05X\t%d
", y, i+1);

 65             if (!vis[y])

 66             {

 67                 vis[y] = i+1;

 68                 pre[y] = x;

 69                 if (y == 0x3FFFF)

 70                     return ;

 71                 Q.push(y);

 72             }

 73         }    

 74     }

 75 }

 76 

 77 void print(int s)

 78 {

 79     if (s == ss) return ;

 80     print(pre[s]);

 81     printf("%d", vis[s]);

 82     if (s != 0x3FFFF) putchar(' ');

 83     else putchar('
');

 84 }

 85 

 86 void init(void)

 87 {

 88     int i, x;

 89     for (ss = i = 0; i < 9; ++i)

 90     {

 91         scanf("%d", &x);

 92         ss |= ((x>>2)<<(i*2));

 93     }

 94     //printf("%0X
", ss);

 95 }

 96 

 97 int main()

 98 {

 99     freopen("clocks.in", "r", stdin);

100     freopen("clocks.out", "w", stdout);

101     

102     init();

103     bfs(ss);

104     print(0x3FFFF);

105     

106     fclose(stdin);

107     fclose(stdout);

108     

109     return 0;

110 }