翻牌游戏,中间一个和上下左右全部反过来,知道全白或者全黑为止。
#include<iostream> using namespace std; int visited[65536]; int queue[65536]; int step[65536]; int front=0; int rear=1; int Flip(int s,int i) { int mstate=s; mstate^=1<<i; if ((i-4)>=0) { mstate ^=1<<(i-4); } if (i%4!=0) { mstate ^= 1<<(i-1); } if ((i+1)%4!=0) { mstate ^= 1<<(i+1); } if (i<12) { mstate ^= 1<<(i+4); } return mstate; } int BFS(int state) { int depth=0; int s,i; queue[front]=state; visited[state]=1; if (state==0 || state==65535) { return 0; } while (front!=rear) { s=queue[front]; front++; for (i=0;i<16;i++) { state=Flip(s,i); if (visited[state]==0) { queue[rear]=state; visited[state]=1; step[state]=step[s]+1; if (state==0 || state==65535) { return 1; } rear ++; } } } return -1; } int main(int argc,char *argv[]) { int state1=0; char str[17]; int i=0; int k; memset(visited,0,sizeof(visited)); memset(queue,0,sizeof(queue)); memset(step,0,sizeof(step)); while (i<16) { cin>>str[i]; if (str[i]=='b') { state1 += 1<<i; } i++; } str[i]='\0'; k=BFS(state1); switch (k) { case -1: cout<<"Impossible"<<endl; break; case 0: cout<<0<<endl; break; case 1: cout<<step[queue[rear-1]]<<endl; break; } return 0; }