UVA10651 Pebble Solitaire【DFS+记忆化搜索+位运算】

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
5
—oo-------
-o–o-oo----
-o----ooo—
oooooooooooo
oooooooooo-o
Sample Output
1
2
3
12
1

问题链接：UVA10651 Pebble Solitaire
问题简述：（略）
问题分析：
    类似于跳棋问题，一维跳棋，计算最少剩下几个棋子。
    需要用到位运算，用记忆化搜索来解决，已经搜索过的状态用按2进制压缩。
程序说明：（略）
参考链接：（略）
题记：（略）

AC的C++语言程序如下：

/* UVA10651 Pebble Solitaire */

#include <bits/stdc++.h>

using namespace std;

const int N = 12;
char s[N + 1];
int dp[4096 + 1];   // 2^12

int dfs(int x)
{
    if(dp[x] != -1) return dp[x];

    int mincnt = 0;
    for(int i = 0; i < N; i++) if(x & (1 << i)) mincnt++;

    for(int i = 0; i < N; i++)
        if(x & (1 << i) && x & (1 << (i + 1))) {    // 第i和i+1位为1
            if(i > 0 && !( x & 1 << (i - 1))) { // 往右跳
                int t = x ^ (1 << i);
                t ^= 1 << (i + 1);
                t ^= 1 << (i - 1);
                mincnt = min(mincnt, dfs(t));
            }
            if(i < N - 2 && !(x & (1 << (i + 2)))) {    // 往左跳
                int t = x ^ (1 << i);
                t ^= 1 << (i + 1);
                t ^= 1 << (i + 2);
                mincnt = min(mincnt, dfs(t));
            }
        }
    return dp[x] = mincnt;
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--) {
        scanf("%s", s);

        int x = 0;
        for(int i = 0; s[i]; i++)
            if(s[i] == 'o') x ^= 1 << i;

        memset(dp, -1, sizeof(dp));
        printf("%d\n", dfs(x));
    }

    return 0;
}