UVA 10651 Pebble Solitaire 鹅卵石摆放记忆化搜索+DFS+记忆化搜索

题意：有12个坑，里面有些鹅卵石，游戏规则：如果有连续的两个鹅卵石，且旁边有个空坑，那可以把旁边的那个鹅卵石跳过空坑中间那个鹅卵石放到空坑里面，而中间那个鹅卵石就被去掉了。

只有12个坑，状态为2^12，才4000多个，所以用stl或是位运算去储存都可以，然后DFS。

我这里用的是位运算+记忆化搜索，好像没有记忆化也不会超时 = =

PS：这就是传说中的状态压缩？

代码：

/* 
*  Author:      illuz  
*  Blog:        http://blog.csdn.net/hcbbt 
*  File:        uva10651.cpp 
*  Create Date: 2013-11-07 20:32:06 
*  Descripton:  dp, bit  
*/  
  
#include   
#include   
  
#define min(a, b) (a) < (b)   (a) : (b)  
  
const int MAXN = 4100;  
  
int vis[MAXN], Min;  
char ch[13];  
  
bool check(int x, int i) {  
    if ((x & (1 << (i - 1))) && (x & (1 << i)) && !(x & (1 << (i + 1))))  
        return true;  
    if (!(x & (1 << (i - 1))) && (x & (1 << i)) && (x & (1 << (i + 1))))  
        return true;  
    return false;  
}  
  
void dp(int x) {  
    if (vis[x]) return;  
    for (int i = 1; i <= 10; i++)  
        if (check(x, i)) {  
            int t = x;  
            t ^= 1 << (i - 1);  
            t ^= 1 << i;  
            t ^= 1 << (i + 1);  
            dp(t);  
        }  
    int cnt = 0;  
    for (int i = 0; i < 12; i++)  
        if (x & (1 << i))  
            cnt++;  
    Min = min(Min, cnt);  
    vis[x] = cnt;  
}  
  
int main() {  
    int n;  
    scanf("%d\n", &n);  
    while (n--) {  
        memset(vis, 0, sizeof(vis));  
        gets(ch);  
        int a = 0;  
        for (int i = 0; i < 12; i++)  
            if (ch[i] == 'o')  
                a |= (1 << i);  
        Min = 13;  
        dp(a);  
        printf("%d\n", Min);  
    }  
    return 0;  
}

UVA 10651 Pebble Solitaire 鹅卵石摆放 记忆化搜索+DFS+记忆化搜索