POJ 2965 The Pilots Brothers' refrigerator 状态压缩+广搜

题意
4*4个开关，每当点击某个开关，该开关及其所在行和所在列的所有开关都会发生改变。给出一组开关状态，求把这组状态变为全开所需的最少步数及相关操作。

样例输入
-+--
----
----
-+--

样例输出
6
1 1
1 3
1 4
4 1
4 3
4 4

思路
状态压缩，BFS暴搜

 1 #include <cstdio>
 2 #include <string.h>
 3 #include <queue>
 4 using namespace std;
 5 const int flip[16] = {0xF888, 0xF444, 0xF222, 0xF111, 0x8F88, 0x4F44, 0x2F22, 0x1F11, 0x88F8, 0x44F4, 0x22F2, 0x11F1, 0x888F, 0x444F, 0x222F, 0x111F};
 6 const int N = 65536;
 7 int cnt[N], path[N], change[N];
 8 
 9 void Print(int x)
10 {
11     if(x)
12     {
13         Print(path[x]);
14         printf("%d %d
", change[x]/4+1, change[x]%4+1);
15     }
16 }
17 
18 void BFS(int x)
19 {
20     bool vis[N] = {0};
21     memset(cnt, -1, sizeof(cnt));
22     vis[0] = true;
23     cnt[0] = 0;
24     queue<int> q;
25     q.push(0);
26     int top, temp;
27     while(!q.empty())
28     {
29         top = q.front();
30         for(int i=0; i<16; ++i)
31         {
32             temp = top ^ flip[i];
33             if(!vis[temp])
34             {
35                 cnt[temp] = cnt[top] + 1;
36                 path[temp] = top;
37                 change[temp] = i;
38                 if(temp == x)
39                 {
40                     printf("%d
", cnt[x]);
41                     Print(x);
42                     return ;
43                 }
44                 vis[temp] = true;
45                 q.push(temp);
46             }
47         }
48         q.pop();
49     }
50 }
51 
52 int main(void)
53 {
54     int x = 0;
55     for(int i=0; i<4; ++i)
56     {
57         for(int j=0; j<4; ++j)
58             x = (x << 1) + (getchar() == '+' ? 1 : 0);
59         getchar();
60     }
61     BFS(x);
62     return 0;
63 }

后来看了这个题解，恍然大悟，又优化了一下代码

http://www.cnblogs.com/Java-tp/p/3873557.html

 1 #include <cstdio>
 2 const int flip[] = {0xF888, 0xF444, 0xF222, 0xF111, 0x8F88, 0x4F44, 0x2F22, 0x1F11, 0x88F8, 0x44F4, 0x22F2, 0x11F1, 0x888F, 0x444F, 0x222F, 0x111F};
 3 int main(void)
 4 {
 5     int x = 0, num = 0;
 6     for(int i=0; i<16; --i)
 7         for(int j=0; j<5; x ^= getchar() == '+' ? flip[i] : 0, ++j, ++i);
 8     for(int temp = x; temp; num += temp&1, temp>>=1);
 9     printf("%d
", num);
10     for(int i=15; ~i; --i, x>>=1)
11         if(x&1)
12             printf("%d %d
", (i>>2)+1, (i&3)+1);
13 }