hdu3278Puzzle

其实最终的结果无非是中间8个方块是相同的颜色，外面16个方块是另外两种颜色。那么其实可以把外面两种颜色看作是0，中间的颜色看做是1。

那么题目就变成了把那种颜色看做1，而其它两种颜色看做0，可以用最少的步骤得到结果。

那么24个方块就可以用24位二进制来标记。那么判重的方式找到了，映射为一个int类型的整数hash

而方块的移动可以看做是位运算的组合，慢慢想想就能够用位运算直接在整数hash上运算，而得到另一个整数。

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <string>
  4 #include <queue>
  5 #include <iostream>
  6 #include <map>
  7 using namespace std;
  8 int q[1<<24];
  9 short step[1<<24];
 10 /*
 11 0 1 2 3 4 5 --> 1 2 3 4 5 0
 12 0 1 2 3 4 5 --> 5 0 1 2 3 4
 13 6 7 8 9 10 11 ->7 8 9 19 11 6
 14 
 15 0 6 12 18 --> 6 12 18 0
 16 0 6 12 18 --> 18 0 6 12
 17 1 7 13 19 --> 7 13 19 1
 18 1 7 13 19 --> 19 1 7 13
 19 4
 20 */
 21 inline int min(const int&a, const int &b)
 22 {
 23     return a < b ? a : b;
 24 }
 25 int tmp[5],c;
 26 int inline col1(int k,int s)
 27 {
 28     c = -1;
 29     for(int i=0; i<4; i++)
 30     {
 31         c -= (1<<(i*6+k));
 32         tmp[i]=s&(1<<(i*6+k));
 33     }
 34     s=s&c;
 35     tmp[0]<<=18;
 36     tmp[1]>>=6;
 37     tmp[2]>>=6;
 38     tmp[3]>>=6;
 39     s=s+tmp[0]+tmp[1]+tmp[2]+tmp[3];
 40     return s;
 41 }
 42 int inline col2(int k,int s)
 43 {
 44     c = -1;
 45     for(int i=0; i<4; i++)
 46     {
 47         c -= (1<<(i*6+k));
 48         tmp[i]=s&(1<<(i*6+k));
 49     }
 50     s=s&c;
 51     tmp[0]<<=6;
 52     tmp[1]<<=6;
 53     tmp[2]<<=6;
 54     tmp[3]>>=18;
 55     s=s+tmp[0]+tmp[1]+tmp[2]+tmp[3];
 56     return s;
 57 }
 58 int inline row1(int k,int s)
 59 {
 60     c = 63<<(k*6);
 61     int tmp = c&s;
 62     s -= tmp;
 63     int t = tmp&(1<<(k*6));
 64     tmp -= t;
 65     tmp>>=1;
 66     tmp +=(t<<5);
 67     return s+tmp;
 68 }
 69 int inline row2(int k,int s)
 70 {
 71     c = 63<<(k*6);
 72     int tmp = c&s;
 73     s -= tmp;
 74     int t = tmp&(1<<(k*6+5));
 75     tmp -= t;
 76     tmp<<=1;
 77     tmp +=(t>>5);
 78     return s+tmp;
 79 }
 80 void bfs()
 81 {
 82     int head = 0,tail = 0;
 83     int cur = 0,tmp,i;
 84     for(i=7; i<=10; ++i)
 85         cur += 1<<i;
 86     for(i=13; i<=16; ++i)
 87         cur+= 1<<i;
 88     step[cur] = 1;
 89     q[tail++] = cur;
 90     
 91     while(head < tail)
 92     {
 93         cur = q[head++];
 94         for(i=0; i<6; ++i)
 95         {
 96             tmp = col1(i,cur);
 97             if(!step[tmp])
 98             {
 99             
100                 step[tmp] = step[cur] + 1;
101                 q[tail++] = tmp;
102             }
103             tmp = col2(i,cur);
104             if(!step[tmp])
105             {
106                 step[tmp] = step[cur] + 1;
107                 q[tail++] = tmp;
108             }
109         }
110         for(i=0; i<4; ++i)
111         {
112             tmp = row1(i,cur);
113             if(!step[tmp])
114             {
115                 step[tmp] = step[cur] + 1;
116                 q[tail++] = tmp;
117             }
118             tmp = row2(i,cur);
119             if(!step[tmp])
120             {
121                 
122                 step[tmp] = step[cur]+ 1;
123                 q[tail++] = tmp;
124             }
125         }
126     }
127 }
128 int main()
129 {
130     int t,k,i,j,w,g,b;
131     scanf("%d",&t);
132     char ch;
133     bfs();
134     for(k=1; k<=t; ++k)
135     {
136         w = g = b = 0;
137         for(i=0; i<4; ++i)
138         {
139             getchar();
140             for(j=0; j<6; ++j)
141             {
142                 scanf("%c",&ch);
143                 if(ch=='B')
144                     b += 1<<(i*6+j);
145                 else if(ch=='G')
146                     g += 1<<(i*6+j);
147                 else
148                     w += 1<<(i*6+j);
149             }
150         }    
151         printf("Case %d: %d
",k,min(step[b]-1,min(step[g],step[w])-1));
152     }
153 }