UVa 10651

another tree structure dp problem, while using bitmask representing state
state:
    dp[i] - minimum pebbles left when reaching state i
transition:
    dp[i]=min(dp[k]), for all k is pre state of i
    leaf nodes are those states can't move any more

/* UVas */
/*****************************************************************************/
int n, b;
int d[1<<12];
string t;
int dfs(int b) {
    int &r=d[b];
    if (r!=-1) {
        return r;
    } else {
        r=INT_MAX;
        for (int i=0; i<12; i++) {
            if ((1<<i)&b) {
                if (((1<<(i-1))&b)&&!((1<<(i-2))&b)&&i>1) {
                    int nb=b&~(1<<i);
                    nb&=~(1<<(i-1));
                    nb|=1<<(i-2);
                    r=min(r, dfs(nb));
                }
                if (((1<<(i+1))&b)&&!((1<<(i+2))&b)&&i<10) {
                    int nb=b&~(1<<i);
                    nb&=~(1<<(i+1));
                    nb|=1<<(i+2);
                    r=min(r, dfs(nb));
                }
            }
        }
        int re=0;
        for (int i=0; i<12; i++) {
            if ((1<<i)&b) {
                re++;
            }
        }
        r=min(r, re);
    }
    return r;
}
int main(void) {
    cin>>n;
    cin.ignore();
    while (n--) {
        getline(cin, t);
        b=0;
        for (int j=0; j<12; j++) {
            int m=11-j;
            b|=t[j]=='o'?1<<m:0<<m;
        }
        memset(d, -1, sizeof(d));
        cout<<dfs(b)<<endl;
    }
    return 0;
}
/*****************************************************************************/