HDU 2209 翻纸牌游戏(双广||状态压缩)

题目链接~~>

                    这题用一般的广搜必定超时，可以用位运算、双向广搜、状态压缩。

方法一：

           位运算：将这一串01数字看成二进制将其转化为十进制。翻纸牌时用位运算解决。重要的一点就是防止异或后超出原有的位数（具体看代码）。

代码（位运算博大精深啊！）：

      #include<stdio.h>
      #include<string.h>
      #include<queue>
      using namespace std ;
      int h ;
      char s[25] ;
      int vis[1200000] ;
      struct zhang
      {
      int x,bu ;
      } ;
      int bfs(int x)
      {
      queue<zhang>q ;
       zhang current,next ;
      memset(vis,0,sizeof(vis)) ;
       current.x=x ;
       current.bu=0 ;
       vis[x]=1 ;
       q.push(current) ;
      while(!q.empty())
       {
       current=q.front() ;
       q.pop() ;
      if(!current.x)
      return current.bu ;
      for(int i=0;i<h;i++)
       {
      if(!i)
       next.x=current.x^3 ;
      else  next.x=current.x^(7<<(i-1)) ;
       next.x=next.x&((1<<h)-1) ;// 防止溢出！！！！如果不这样有可能超出h位。
      if(vis[next.x])
      continue ;
       next.bu=current.bu+1 ;
       vis[next.x]=1 ;
       q.push(next) ;
       }
       }
      return  -1 ;
      }
      int main()
      {
      int i ;
      while(scanf("%s",s)!=EOF)
       {
       h=strlen(s) ;
      int k=1,sum=0 ;
      for(i=0;i<h;i++)
       {
       sum+=(s[i]-'0')*k ;
       k=k*2 ;
       }
      int mx=bfs(sum) ;
      if(mx!=-1)
      printf("%d\n",mx) ;
      else printf("NO\n") ;
       }
      return 0 ;
      }
  
 

本人暂且研究了这一种方法其它方法以后补充。。。

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/14053743