(BitMask) UVa - 10651 - Pebble Solitaire

/**
@author - Rumman BUET CSE'15
Problem - UVa   10651   Pebble Solitaire

Concept - Bit mask DP

Idea - এটা আমার জীবনে প্রথম বিট্মাস্ক ডিপি প্রব্লেম ।

প্রশ্ন পড়লেই বুঝা যায় কি করা লাগবে । আমি প্রথমে লুপ চালাইসি । দেখসি এটা ১ কি না । যদি ১ হয় , তাইলে চেষ্টা করবো ডানে বা বামে যাবার ।
ডানে বা বামে যাবো কি না সেটা ডিপেন্ড করবে শর্ত দেয়া আছে ওই ২ টা শরতের উপর । তো  ধরি , বামে গেলাম রিকারসিভ কলের মাধ্যমে ।
ওইখান থেকে একটা অ্যান্সার রিটার্ন করবে । এই এন্সার কি আগের এন্সারের চেয়ে ছোট ? তাইলে এটা । নাইলে আগের টা এন্সার ।
এবার ডানে যাবো । একই ভাবে এন্সার পাবো ।

পুরা বিট্মাস্কের শুরু থেকে শেষ পর্যন্ত এভাবে লুপ চালায়ে যাবো । এন্সারে লাস্ট পর্যন্ত যা থাকবে তাই এন্সার ।

শিক্ষাঃ ***** আমার সেট , রিসেট ফাংশনে রেফারেন্স ভ্যারিয়েবল দিসি । সো , এসব ইউজ করলে পারমানেটলি ভ্যালু চেঞ্জ হয়ে যাবে । সো , এসব ইউজের সময় সাবধান !!!


**** কোন একটা স্টেটে কাজ করার সময় ভুলেও ওই স্টেটের বিট্মাস্ক জীবনে ও পারমানেন্টলি চেঞ্জ করা যাবে না ।
যদি পরের স্টেটে রিকারশনে পাঠাতে হয় , তাইলে আরেক ভ্যারিয়েবলের মধ্যে এটাকে ঢুকাও । এরপর ওটাকে চেঞ্জ করে পাঠাও ।

***** এক সল্যুশন দেখলাম সল্ভের পর । GCC এর বিল্ট ইন ফাংশন আছে । বিট্মাস্কে কয়টা ১ আছে বলার জন্য । এটা ভালো । ইউজ করা যাবে ।

এটা হলো -    "__builtin_popcount(mask)"


*/

// LightOJ always needs this format for sure..so I made a copy of it...
#include <bits/stdc++.h>
#include<vector>
#define ll                                      long long int
#define fi                                      freopen("in.txt", "r", stdin)
#define fo                                      freopen("out.txt", "w", stdout)
#define m0(a) memset(a , 0 , sizeof(a))
#define m1(a) memset(a , -1 , sizeof(a))
#define inf INT_MAX
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))

#define ones(mask)  __builtin_popcount(mask) /// __builtin_popcount : it's a built in function of GCC. Finds out the numbers of 1 in binary representation.

#define mx 150000

using namespace std;

string s ;

int Set(int &N,int pos)
{
    return N=N | (1<<pos);
}
int reset(int &N,int pos)
{
    return N= N & ~(1<<pos);
}
bool check(int N,int pos)
{
    return (bool)(N & (1<<pos));
}

int N ;
int dp[(1<<12) + 5] ;


int solve(int mask)
{
    if(dp[mask] != -1)
    {
        return dp[mask] ;
    }

    int ans = ones(mask) ;

    for(int i = 0 ; i < N ; i++)
    {
        if(check(mask, i))
        {

            if(i+2 <= N-1 && check(mask, i) && check(mask, i+1) && !check(mask, i+2) )
            {
                int m = mask ;
                reset(m, i) ;
                reset(m, i+1) ;
                Set(m, i+2) ;
                ans = min(ans, solve(m)) ;
            }

            if(i-2 >= 0 && check(mask, i) && check(mask, i-1) && !check(mask, i-2))
            {
                int m = mask ;
                reset(m, i) ;
                reset(m, i-1) ;
                Set(m, i-2) ;
                ans = min(ans, solve(m)) ;
            }
        }
    }

    return dp[mask] = ans ;
}


int main()
{
//    fi ;
//    fo ;
    ll T, t = 0 ;
    scanf("%lld",&T) ;

    while(T--)
    {
        m1(dp) ;
        t++ ;
        cin >> s ;

        N = s.size() ;
        int mask  = 0 ;

        for(int i = 0 ; i < N ; i++)
        {
            if(s[i] == 'o')
            {
                Set(mask, N-1-i) ;
            }
        }

        cout << solve(mask) << endl  ;
    }
    return 0 ;
}