POJ 1753-Flip Game Flip Game Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 31655 Accepted: 13776 Description Flip game is played on a rectangular 4×4 field with two-sided pieces placed on each of its 16 squares. One side of each piece is white and the other one is black and each piece is lying either it’s black or white side up. Each round you flip 3 to 5 pieces, thus changing the color of their upper side from black to white and vice versa. The pieces to be flipped are chosen every round according to the following rules: Choose any one of the 16 pieces. Flip the chosen piece and also all adjacent pieces to the left, to the right, to the top, and to the bottom of the chosen piece (if there are any). Consider the following position as an example: bwbw wwww bbwb bwwb Here “b” denotes pieces lying their black side up and “w” denotes pieces lying their white side up. If we choose to flip the 1st piece from the 3rd row (this choice is shown at the picture), then the field will become: bwbw bwww wwwb wwwb The goal of the game is to flip either all pieces white side up or all pieces black side up. You are to write a program that will search for the minimum number of rounds needed to achieve this goal. Input The input consists of 4 lines with 4 characters “w” or “b” each that denote game field position. Output Write to the output file a single integer number – the minimum number of rounds needed to achieve the goal of the game from the given position. If the goal is initially achieved, then write 0. If it’s impossible to achieve the goal, then write the word “Impossible” (without quotes). Sample Input bwwb bbwb bwwb bwww Sample Output 4 Source Northeastern Europe 2000

---

题意：翻动格子使得整个棋盘为全黑或者全白，求最少的翻动次数，翻动某一个格子，也会同时翻动其周围的四个格子（如果有的话）。因为某一个格子翻动2次的结果和不翻是一样的；翻动3次的结果和翻动1次的结果是一样的；多个也是一样，所以一个格子最多翻动1次，这样总的翻动次数最多为16次。每个格子有翻和不翻两种情况，所以总共有$$2^{16}$$种情况，可以暴力枚举。 但是一直没有想好用哪种方法，深度搜索还是广度搜索。后来想了想，这是求最优解（最少翻动次数）的题，所以用广度优先搜索的效率应该会高一些，但是在BFS的过程中曾有一个问题困扰了，后面再说。又因为棋盘正好是4*4=16的，可以用int的位运算来表示，b表示1，w表示0，这样棋盘的一个状态就可以用一个int数来表示，翻动格子也可以用位运算来表示，总共的状态数是$$2^{16}$$，取值范围是[0,65535]，当棋盘状态是0或者65535时，表示全白或者全黑，这时找到结果。 了解了这些，就可以写出BFS+位运算的代码了，这题我是参考了网上的题解： [cpp] #include<iostream> #include<queue> using namespace std; const int MAX_STATUS=65536;//2^16=65536种，所以[0,65535] const int ALL_0=0;//全0 const int ALL_1=65535;//全1 int ans; int visited[MAX_STATUS]={0};//访问标记 typedef struct POS//position翻转位置 { int val;//当前翻转状态的值 int step;//到当前状态共翻转了多少次 }; //广搜 void BFS(int init_id) { queue<POS> Q_P; POS s,next_p; //初始位置 s.val=init_id; s.step=0; visited[s.val]=1; Q_P.push(s); while(!Q_P.empty()) { s=Q_P.front(); Q_P.pop(); if(s.val==ALL_0||s.val==ALL_1)//找到结果 { ans=s.step; return; } //尝试翻16个位置 for(int i=0;i<4;i++) { for(int j=0;j<4;j++) { next_p.val=s.val; //测试i，翻转[i,j]上下位置的格子 if(i==0) next_p.val^=1<<(11-4*i-j); else if(i==3) next_p.val^=1<<(19-4*i-j); else { next_p.val^=1<<(11-4*i-j); next_p.val^=1<<(19-4*i-j); } //测试j，翻转[i,j]左右位置的格子 if(j==0) next_p.val^=3<<(14-4*i-j); else if(j==3) next_p.val^=3<<(15-4*i-j); else next_p.val^=7<<(14-4*i-j); if(visited[next_p.val]==0)//如果没有访问 { visited[next_p.val]=1;//访问 next_p.step=s.step+1;//翻转次数加1 Q_P.push(next_p);//并加入队列 } } } } ans=-1;//到这里还没有return,说明impossible } int main() { //freopen("input.txt","r",stdin); char c; int id=0; //输入转换 /*bwbw wwww bbwb bwwb 排列成bwbw wwww bbwb bwwb，然后把b换成1，w换成0*/ for(int i=0;i<4;i++) { for(int j=0;j<4;j++) { cin>>c; id<<=1; if(c==’b’)//b=1;w=0 id+=1; } } BFS(id); if(ans==-1) cout<<"Impossible"; else cout<<ans; return 0; } [/cpp] 本代码提交AC，用时79MS，内存508K。 在每一次BFS的时候，我们都要尝试去翻所有16个格子，如果翻动之后达到了一个新的状态（也就是之前没有访问过），说明这个翻动是有效的，把它加入到队列中。在翻动的时候，怎样进行位运算大家可以把i=0,j=0代入到for循环里手算一遍，程序会根据i和j的不同，和不同的数进行异或运算。 之前我说有一个地方让我困惑，就是我之前：第一次BFS的时候肯定把所有格子都翻了一遍，也就是把(0,0)(0,1)…(3,3)翻动的结果都加入到队列中了，那么在第二次BFS的时候，把(0,0)出队，这个时候再来翻所有16个格子，这样不就相当于把所有格子又翻回到初始状态了吗？其实这种想法是不对的，说到底还是对BFS理解不够透彻。**我们在每次BFS的时候都是在队首元素的基础上翻转的，因为我们在while开头执行了s=Q_P.front();Q_P.pop();这么两句**，那么当我们把(0,0)翻转状态出队在去翻转的时候，是在(0,0)翻转状态的基础是再进行翻转的，而这个时候是只有(0,0)这一个格子翻了，其他15个格子都没有翻；同理当把(0,1)出队的时候，也是只有(0,1)翻了，其他15个都没有翻。所以这样BFS下去是能够搜索到所有状态的。 纵观所有BFS题目，套路都是一样的。]]>