uva10651

제목의 대의: 바둑을 두는 것과 유사하게 마지막에 몇 개 남았으면 좋겠다.
사고방식: 비트 연산 + 기억화 검색 상태 압축
코드:

#include <iostream>
using namespace std;
#include <stdio.h>
#include <cstring>
const int MAXN = 4100;
int vis[MAXN],_min;
char s[15];
bool check(int k,int i) {
    if((k & (1 << (i - 1))) && (k & (1 << i)) && !(k & (1 << (i + 1)))) //oo-    
        return true;
    if(!(k & (1 << (i - 1))) && (k & (1 << i)) && (k &(1 << (i + 1))))//-oo    
        return true;
    return false;
}
void dp(int k) {
    if(vis[k])
        return ;
    for(int i = 1; i <= 10; i++) {
        int t = k;
        if(check(k,i)) { //        
            t ^= (1 << (i - 1));
            t ^= (1 << i);
            t ^= (1 << (i + 1));
            dp(t);
        }
    }
    int cnt = 0;
    for(int i = 0; i < 12; i++) 
        if(k & (1 << i))
            cnt++;
    _min = min(_min,cnt);
    vis[k] = cnt;
}
int main() {
    int n;
    scanf("%d",&n);
    getchar();
    while(n--) {
        gets(s);
        int a = 0;
        for(int i = 0; i < 12; i++)
            if(s[i] == 'o')
                a |= (1 << i);
        memset(vis,0,sizeof(vis));
        _min = 13;
        dp(a);
        printf("%d
",_min);
    }
    return 0;
}