我希望通过博客的形式记录自己项目和基础积累的过程，这篇是算法以及程序设计的开篇。
题目：poj1753 Flip Game Time:1000MS Mem:65536K
描述：黑白两面的棋子，给一个4*4棋盘，每轮可以翻动其中任意一个棋子，使其由白变黑（或由黑变白），其周围上、下、左、右的棋子（如果存在）也一起变色。目标是使得棋盘上全部棋子为全黑（或全白）。
输出：达到全黑（或全白）的最小轮次。如果不能达到，输出 "Impossible"。
类别：BFS
分析：对于整个棋盘来说，每一格只有黑白（01）两种情况，总共有2^16=65536种。考虑用unsigned short类型每一位存储每一个格中的内容，进行编码。
创建队列，对初始情况中的每一个棋子做翻转，查看其是否满足全黑||全白，满足则输出轮次返回，不满足则继续考察是否之前出现过此种排列，如果没出现过，则进入队列，否则不进行操作。
加标记变量记录每一轮开始元素下标，如果当前队头是每一轮的第一个元素，则轮次加一。
如果队列为空，则输出Impossible返回。
1 //20130111 POJ1753 2 //result: 20130113 452K 32MS C 1837B 3 #include <stdio.h> 4 5 #define MAX_LEN 65536 6 7 int flag[0xFFFF] = {0}; //mark down which kind of mat has shown 8 unsigned short queue[MAX_LEN] = {0}; //flip steps queue 9 unsigned short flip[16] = {0x13, 0x27, 0x4E, 0x8C, 0x131, 0x272, 0x4E4, 0x8C8, 0x1310, 10 0x2720, 0x4E40, 0x8C80, 0x3100, 0x7200, 0xE400, 0xC800}; 11 unsigned short t[16] = {1, 2, 4, 8, 16, 32, 64, 128, 12 256, 512, 1024, 2048, 4096, 8192, 16384, 32768}; 13 14 int main() 15 { 16 int i, j, p; 17 int count = 0; 18 unsigned short value = 0,current = 0; 19 int rear = 1; 20 int front = 0; 21 char ch; 22 23 for (i = 0; i < 4; i++) { 24 for (j = 0; j < 4; j++) { 25 scanf("%c", &ch); 26 if (ch == 'w') 27 value |= t[4 * i + j]; 28 } 29 getchar(); 30 } 31 //printf("10:%d - 16:%x\n", value, value); //test 32 33 if (value == 0 || value == 0xFFFF) { 34 printf("0\n"); 35 return 0; 36 } 37 p = 1; //the start of each layer 38 queue[0] = value; 39 while (front != rear) { 40 for (j = 0; j < 16; j++) { 41 current = queue[front] ^ flip[j]; 42 if ((current == 0) || (current == 0xFFFF)) { 43 printf("%d\n", count+1); 44 return 0; 45 } 46 if (flag[current] == 0) { //if not shown even once, push to the queue 47 queue[rear] = current; 48 rear++; //I don't know whether to check if 'rear' is over the boundary or not. I think it won't bigger than 0xFFFF 49 flag[current] = 1; 50 } 51 } 52 front++; 53 if (front == p) { //mark the start of each layer(BFS) 54 count++; 55 p = rear; 56 } 57 } 58 printf("Impossible"); 59 60 return 0; 61 }错误总结：
1. 最最最最最最让我蛋疼的就是，我在手写flip[]的时候，从纸上往vs里居然少誊写了一个。马虎是万恶之首
2. 在对BFS的理解上还不够清晰，应该是每一层的情况都判断过合理与否之后再进入下一层。我刚开始写的时候并没有注意到这一点，导致程序结构比较混乱。
3. 这差不多是我第一次应用到位运算，在了解了^异或运算之余，顺便了解了& | << >>等等在实际应用中可以发挥很大作用的位运算们，这两天还要专门看一下。
4. 队列这次并没有涉及循环队列，也就没有涉及到对空间复杂度以及同一时间空间占用量的分析，在和清华讨论的过程中提到了这个问题，但是没有深入。
5. 标记变量的合理使用会使得事情简单不少。
转载于:https://www.cnblogs.com/wynemo/archive/2013/01/13/2858241.html
相关资源：poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告