Flip Game--POJ 1753

有一段时间没有做acm题目了，感觉智商下降了不少，这倒状态压缩枚举题，以前没有做过，还是最简单的一题，所以结果可想而知，忧伤，可还是不想放弃。

看了别人的思路，遇上一个十分诡异的错误，应该是数组开小了，结果无符号变成有符号的数，结果悲剧了。改了好久才发现错误，得到的教训就是以后一定要把数组开大一些。

题目链接：http://poj.org/problem?id=1753

解题思路大体是这样的：

1.使用16位的unsigned short 整形数来表示每个单元格的状态。

2.使用广度优先搜索来拓展节点，队列使用数组表示。

 1 #include<iostream>
 2 using namespace std;
 3 unsigned short qState[100000];
 4 bool flag[100000];
 5 int step[100000];
 6 
 7 int top=0;
 8 int rear=0;
 9 void init()
10 {
11     char c;
12     unsigned short int temp=0;
13      for(int i=0; i < 4; i++)
14         for(int j = 0; j < 4; j++)
15         {
16             cin>>c;
17             if('b' == c)
18                 temp |= (1<<(i*4+j));
19         }
20     //printf("
");
21     //step[temp]=0;
22   //  printf("init:
");
23    // print(temp);
24    // getchar();
25    // getchar();
26     qState[rear++]=temp;
27     flag[temp]=true;
28 }
29 unsigned short flip(unsigned short state,int i)
30 {
31     unsigned short temp=0;
32     temp|=(1<<i);
33     if(i%4!=0)
34     {
35        temp|=(1<<(i-1));
36     }
37     if((i+1)%4!=0)
38     {
39        temp|=(1<<(i+1));
40     }
41     if(i+4<16)
42     {
43         temp|=(1<<(i+4));
44     }
45     if(i-4>=0)
46     {
47         temp|=(1<<(i-4));
48     }
49     //print(state);
50    // printf("
");
51    // print(temp);
52     return (state^temp);
53 }
54 bool BFS()
55 {
56    // printf("in BFS:
");
57     while(top<rear)
58     {
59         unsigned short state=qState[top++];
60         for(int i=0;i<16;i++)
61         {
62             unsigned short temp;
63             temp=flip(state,i);
64             if(state==0||state==65535)
65             {
66                 cout<<step[state];
67                 return true;
68             }
69             else if(!flag[temp])
70             {
71                 flag[temp]=true;
72                 step[temp]=step[state]+1;
73                 qState[rear++]=temp;
74             }
75         }
76     }
77     return false;
78 }
79 int main()
80 {
81     init();
82     if(!BFS())
83     {
84         cout<<("Impossible
");
85     }
86     //cout<<"rear: "<<rear<<endl;
87     return 0;
88 }

View Code