POJ 1753 Flip Game（状态压缩）

题目链接~~>

做题感悟：开始没好好读题，认为单个棋子也可以翻，那样的话就不可能出现 Impossible 的情况了，这说明没好好读题，既然题目给出 Impossible 那一定会有用，先用 dfs 暴力做的，然后看到网上有人用状态压缩，唉，我怎么没想到呢！（应该反思一下，毕竟也是做过几个状态压缩题的人，竟然没想到。）只能说一句：状态压缩太神奇了!

解题思路：因为题目只有 16 个位，所以转化为二进制没问题（和HDU 翻纸牌差不多）。这样图就可以标记了。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      char s[6] ;
     
    
   

    

     

    
    

     

      bool vis[150005] ;
     
    
   

    

     

    
    

     

      int p[20]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072} ;
     
    
   

    

     

    
    

     

      struct zhang
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int x,step ;
     
    
   

    

     

    
    

     

      } ;
     
    
   

    

     

    
    

     

      int search(int x,int temp) // 变化上下左右
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if(x+4<16)  // 下
     
    
   

    

     

    
    

     

       temp^=p[x+4] ;
     
    
   

    

     

    
    

     
 if(x-4>=0)   // 上
     
    
   

    

     

    
    

     

       temp^=p[x-4] ;
     
    
   

    

     

    
    

     
 if(x%4>0)   //右
     
    
   

    

     

    
    

     

       temp^=p[x-1] ;
     
    
   

    

     

    
    

     
 if(x%4<3)   // 左
     
    
   

    

     

    
    

     

       temp^=p[x+1] ;
     
    
   

    

     

    
    

     
 return temp ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int bfs(int sum)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int temp ;
     
    
   

    

     

    
    

     
 queue<zhang>q ;
     
    
   

    

     

    
    

     

       zhang curt,next ;
     
    
   

    

     

    
    

     
 memset(vis,false,sizeof(vis)) ;
     
    
   

    

     

    
    

     

       curt.x=sum ;
     
    
   

    

     

    
    

     

       curt.step=0 ;
     
    
   

    

     

    
    

     

       vis[sum]=true ;
     
    
   

    

     

    
    

     

       q.push(curt) ;
     
    
   

    

     

    
    

     
 while(!q.empty())
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       curt=q.front() ;
     
    
   

    

     

    
    

     
 if(!curt.x||curt.x==65535)
     
    
   

    

     

    
    

     
 return  curt.step ;
     
    
   

    

     

    
    

     

       q.pop() ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<16 ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       next.step=curt.step+1 ;
     
    
   

    

     

    
    

     

       temp=curt.x^p[i] ;
     
    
   

    

     

    
    

     

       temp=search(i,temp) ;
     
    
   

    

     

    
    

     
 if(vis[temp])
     
    
   

    

     

    
    

     
 continue ;
     
    
   

    

     

    
    

     

       next.x=temp ;
     
    
   

    

     

    
    

     

       vis[temp]=true ;
     
    
   

    

     

    
    

     

       q.push(next) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return -1 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int i,j,sum=0 ;
     
    
   

    

     

    
    

     
 for(i=0 ;i<4 ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%s",s) ;
     
    
   

    

     

    
    

     
 for(j=0 ;j<4 ;j++)
     
    
   

    

     

    
    

     
 if(s[j]=='b') // 压缩图
     
    
   

    

     

    
    

     

       sum=sum^p[i*4+j] ; 
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 int mx=bfs(sum) ;
     
    
   

    

     

    
    

     
 if(mx!=-1)
     
    
   

    

     

    
    

     
 printf("%d\n",mx) ;
     
    
   

    

     

    
    

     
 else printf("Impossible\n") ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

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

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