Pebble solitaire is an interesting game. This is a game where you are given a board with an arrangement of small cavities, initially all but one occupied by a pebble each. The aim of the game is to remove as many pebbles as possible from the board. Pebbles disappear from the board as a result of a move. A move is possible if there is a straight line of three adjacent cavities, let us call them A, B, and C, with B in the middle, where A is vacant, but B and C each contain a pebble. The move constitutes of moving the pebble from C to A, and removing the pebble in Bfrom the board. You may continue to make moves until no more moves are possible.

In this problem, we look at a simple variant of this game, namely a board with twelve cavities located along a line. In the beginning of each game, some of the cavities are occupied by pebbles. Your mission is to find a sequence of moves such that as few pebbles as possible are left on the board.

Input

The input begins with a positive integer n on a line of its own. Thereafter n different games follow. Each game consists of one line of input with exactly twelve characters, describing the twelve cavities of the board in order. Each character is either ‘-‘ or ‘o‘ (The fifteenth character of English alphabet in lowercase). A ‘-‘ (minus) character denotes an empty cavity, whereas a ‘o‘ character denotes a cavity with a pebble in it. As you will find in the sample that there may be inputs where no moves is possible.

Output

For each of the n games in the input, output the minimum number of pebbles left on the board possible to obtain as a result of moves, on a row of its own.

Sample Input                              Output for Sample Input

Swedish National Contest

问最后最少留下的数：oo- -->--o,-oo -->o--

d[s]代表s串最多可去掉的数;每步可减去一个.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
typedef long long LL;
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
map<string,int>d;
string str,t;
int n,ans;
int dp(string s)
{
    if(d[s]>0)  return d[s];
    d[s]=1;
    for(int i=0;i<10;i++)
    {
        if(s[i]=='o'&&s[i+1]=='o'&&s[i+2]=='-')
        {
            t=s;
            t[i]=t[i+1]='-';
            t[i+2]='o';
            d[s]=max(d[s],dp(t)+1);
        }
        if(s[i]=='-'&&s[i+1]=='o'&&s[i+2]=='o')
        {
            t=s;
            t[i]='o';
            t[i+1]=t[i+2]='-';
            d[s]=max(d[s],dp(t)+1);
        }
    }
    return d[s];
}
int main()
{
     std::ios::sync_with_stdio(false);
     cin>>n;
     while(n--)
     {
         cin>>str;
         ans=1;
         REP(i,12)
            if(str[i]=='o')   ans++;
        ans-=dp(str);
        cout<<ans<<endl;
     }
     return 0;
}

UVA 10651 Pebble Solitaire（记忆化）