UVA 10651 --Pebble Solitaire +dfs

这道题有两种做法：搜索和状态压缩dp

因为这个题的状态只要2^12,所以可以用dfs或bfs将所有的可达状态走一遍，然后就可以得到答案了。

我是用二进制压缩以后再进行的dfs；其实也可以直接开一个12位长度数组表示状态，然后dfs或bfs，这样

状态判重可以用hash或二进制压缩。

状态压缩dp的话，现在还没看，就放到以后再研究去了。

代码如下：

#include
  
   
#include
   
     #include
    
      using namespace std; int vis[5000],ans; void dfs(int st) { int a[20]; int k=0; memset(a,0,sizeof(a)); while(st) { a[k++]=st%2; st/=2; } k=12; for(int i=k-1;i>=2;i--) { if(a[i]==0&&a[i-1]==1&&a[i-2]==1) { int b[30]; for(int j=0;j
     
      =0;j--) { if(b[j]==1) cnt++; if(b[j]==1) sum=sum*2+1; else sum=sum*2; } if(cnt!=0&&cnt
      
       =0;j--) { if(b[j]==1) cnt++; if(b[j]==1) sum=sum*2+1; else sum=sum*2; } if(cnt!=0&&cnt