首页 > 代码库 > poj 1753 Flip Game
poj 1753 Flip Game
先贴个BFS+位运算的代码:
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>using namespace std;unsigned short q[65536],rear,top,step[65536];//(2^16)-1bool vis[65536];unsigned short temp;bool bfs(){ memset(q,0,sizeof(q)); memset(vis,0,sizeof(vis)); rear=top=0; q[top++]=temp; step[temp]=0; while(rear<top){ temp=q[rear++]; if(temp==0||temp==65535){ cout<<step[temp]<<endl; return true; } short i=0; for(;i<16;i++){ unsigned short ex=0; ex|=1<<i; if(i>3){ ex|=1<<(i-4); } if(i<12){ ex|=1<<(i+4); } if(i%4){ ex|=1<<(i-1); } if((i+1)%4){ ex|=1<<(i+1); } ex=ex^temp; if(!vis[ex]){ vis[ex]=true; q[top++]=ex; step[ex]=step[temp]+1; } } } return false;}int main(){ //freopen("D:\\INPUT.txt","r", stdin); short i=0; temp=0; for(;i<16;i++){ char c; cin>>c; //cout<<c<<endl; if(c==‘b‘){ temp|=(1<<i); } } if(!bfs()){ cout<<"Impossible\n";//"\b"打成"/n",WA } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。