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