USACO sec1.4 The Clocks

用的BFS，将每一个数字除以4，得到四种不同的状态：0 1 2 3，为了实现判重，用2位表示一个状态，整个钟表需要2*9 = 18位，不大；

题解中第二种做法貌似是推理得到了一般解法。

  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\n", 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('\n');
 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\n", 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 }