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