Problem A
Pebble Solitaire
Input: standard input
Output: standard output
Time Limit: 1 second
 

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 B from 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

鵝卵石接龍，一排十二個鵝卵石，就跟跳棋很像，一個鵝卵石藉由另外一個鵝卵石跳到空白的地方，此時被跨過的那顆鵝卵石會消失，問最後最少會剩下多少顆。

其實這題可以用 BFS 去找的，把答案全部找出來其實也是不錯的。

#include <stdio.h>
#include <string.h>
int ans[1<<12];
int dp(int n) {
    if(ans[n] != -1)
        return ans[n];
    int i, j = 0, tmp, x;
    ans[n] = 0xffff;
    for(i = 0; i < 10; i++) {
        if(((n>>i)&1) && ((n>>(i+1))&1) && !((n>>(i+2))&1)) {
            x = n;
            x ^= 1<<i;
            x ^= 1<<(i+1);
            x ^= 1<<(i+2);
            tmp = dp(x);
            if(tmp < ans[n])    ans[n] = tmp;
            j = 1;
        }
        if(!((n>>i)&1) && ((n>>(i+1))&1) && ((n>>(i+2))&1)) {
            x = n;
            x ^= 1<<i;
            x ^= 1<<(i+1);
            x ^= 1<<(i+2);
            tmp = dp(x);
            if(tmp < ans[n])    ans[n] = tmp;
            j = 1;
        }
    }
    if(j == 0) {
        ans[n] = 0;
        for(i = 0; i < 12; i++)
            if((n>>i)&1)    ans[n]++;
    }
    return ans[n];
}
int main() {
    memset(ans, -1, sizeof(ans));
    int t, i, n;
    char s[20];
    scanf("%d", &t);
    while(t--) {
        scanf("%s", s);
        n = 0;
        for(i = 0; i < 12; i++)
            if(s[i] == 'o')
                n |= 1<<i;
        printf("%d\n", dp(n));
    }
    return 0;
}