hdu2209 翻纸牌游戏-位运算bfs
hdu2209
#include<iostream>#include<cstdio>#include<cstring>#include<queue>using namespace std;bool vis[1<<20];int path[1<<20],len;queue<int>Q;int bfs(int x){int X;if(!x)return 0;while(!Q.empty())Q.pop();Q.push(x);vis[x]=1;path[x]=0;while(!Q.empty()){x=Q.front();Q.pop();for(int i=1;i<=len;i++){if(i==1)X=x^3;//翻前两个elseX=x^(7<<(i-2));//翻三个//printf("%d ",X);system("pause");X&=(1<<len)-1;if(vis[X])continue;vis[X]=1;path[X]=path[x]+1;if(X==0)return path[X];Q.push(X);}}return -1;}int main(){int i,j,k,x;char s[30];while(scanf("%s",s)!=EOF){len=strlen(s);for(x=i=0;i<len;i++)x=(x<<1)+s[i]-'0';memset(vis,0,sizeof(vis));memset(path,0,sizeof(path));x=bfs(x);if(x==-1)printf("NO\n");elseprintf("%d\n",x);}return 0;}