本文主要是介绍POJ-1753:Flip Game(位存储)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本题在上一篇文章（http://blog.csdn.net/smarteryu/article/details/9212693）中已经给出了问题描述和一种做法，这里是区别于上一种做法的另外一个方法。其实思想还是一样的，都是深搜遍历尽所有的情况，只不过这里考虑到了一共十六个棋各而每种棋格有两种状态，正好可以用一个16bits的变量来存储，目标状态就是该变量的数值是0或者65535。同时在遍历的过程中用到了队列的思想辅之一个标志数组来使得状态不会出现重复的现象。
具体代码：
#include<iostream>
#include<fstream>
using namespace std;#define max 65536int que[max];//存储状态的队列
int vis[max];//标识是否操作的数组
int step[max];//记录到当前状态已经进行的反转次数
int head=0;
int rear=0;int main()
{freopen("data.in","r",stdin);char ch;int chess=0;for(int i=0;i<4;i++)//输入操作{for(int j=0;j<4;j++){cin>>ch;chess=chess<<1;if('w'==ch){chess++;}}}que[rear++]=chess;//初始状态进队vis[chess]=1;step[chess]=0;while(head<rear)//开始迭代，结束的条件是队列为空{int now=que[head++];int temp;if(now==0||now==65535)//当前状态满足了要求条件{cout<<step[now]<<endl;return 0;}for(int n=0;n<16;n++)//把取出的状态按照不同的位置进行16次变换操作{temp=now;int i=n/4;int j=n%4;int m=15-n;//进行变换temp=temp^(1<<m);if(i>0)temp=temp^(1<<(m+4));if(i<3)temp=temp^(1<<(m-4));if(j>0)temp=temp^(1<<(m+1));if(j<3)temp=temp^(1<<(m-1));if(!vis[temp])//如果是一个新的状态，则入队{que[rear++]=temp;step[temp]=step[now]+1;vis[temp]=1;}}}cout<<"Impossible"<<endl;//没有找到符合题意的变换return 0;
}
这篇关于POJ-1753:Flip Game(位存储)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
