http://poj.org/problem?id=1753
题意：有一个4*4的方格，每个方格中有一粒棋子，棋子一面为白色，一面为黑色。每次翻转一粒棋子，则它周围的棋子也随之翻转，直至方格全为黑棋或全为白棋，输出最少的翻转次数，如果不可能达到此种状态，输出Impossible。
1 #include<stdio.h> 2 #include<string.h> 3 #include<queue> 4 #include<iostream> 5 using namespace std; 6 struct node 7 { 8 int step;//步数 9 int state;//状态 10 }; 11 int vis[65538]; 12 int f[16] = 13 { 14 51200,58368,29184,12544,35968,20032,10016,4880,2248,1252,626,305,140,78,39,19 15 };//16种状态转换 16 int bfs(int state1) 17 { 18 19 queue<struct node>q; 20 struct node pre,next; 21 pre.state = state1; 22 pre.step = 0; 23 q.push(pre); 24 vis[state1] = 1;//标记已被访问过的状态 25 while(!q.empty()) 26 { 27 pre = q.front(); 28 q.pop(); 29 if(pre.state==0 || pre.state==65535) 30 return pre.step; 31 for (int i = 0; i < 16; i ++) 32 { 33 next.state = pre.state^f[i];//异或产生新状态 34 next.step = pre.step + 1; 35 if(next.state==0 || next.state==65535) 36 return next.step; 37 if(!vis[next.state]) 38 q.push(next);//进队列 39 vis[next.state] = 1; 40 } 41 } 42 return -1; 43 } 44 int main() 45 { 46 int i,j; 47 int state = 0; 48 char str[5][5]; 49 memset(vis,0,sizeof(vis)); 50 for (i = 0; i < 4; i ++) 51 scanf("%s",str[i]); 52 for (i = 0; i < 4; i ++) 53 { 54 for (j = 0; j < 4; j ++) 55 { 56 state <<= 1;//转换成二进制 57 if (str[i][j]=='b') 58 state+=1; 59 } 60 } 61 int ans = bfs(state); 62 if(ans == -1) 63 printf("Impossible "); 64 else 65 printf("%d ",ans); 66 return 0; 67 }