[UVa] 10651 Pebble Solitaire.cpp

#include <cstdio>
#include <queue>
using namespace std;
#define BACKTRACKING

#ifdef BITMASK
int main()
{
    int T;
    char line[15];
    scanf("%d", &T);
    while (T--) {
        // Input
        scanf("%s", &line);
        unsigned int board = 0;
        int num = 0;
        for (int i = 0; i < 12; ++i) {
            board <<= 1;
            if (line[i] == 'o') {
                board |= 1;
                ++num;
            }
        }
        // dp: bitmask
        int dp[1<<12] = {0};
        queue<unsigned int> Q;
        int Min = 99;

        Q.push(board);
        dp[board] = num;

        // bfs
        while (!Q.empty()) {
            unsigned int cur = Q.front();
            Min = min(Min, dp[cur]);
            Q.pop();

            for (int i = 0; i < 12; ++i) {
                if (cur & (1<<i)) {
                    if (i>=2 && (cur & (1<<(i-1))) && !(cur & (1<<(i-2)))) {
                        unsigned int nxt = cur;
                        nxt = nxt & (~(1<<i)) & (~(1<<(i-1)));  // unset i and i-1
                        nxt = nxt | (1<<(i-2)); //set i-2
                        dp[nxt] = dp[cur] - 1;
                        Q.push(nxt);
                    }
                    if (i<=9 && (cur & (1<<(i+1))) && !(cur & (1<<(i+2)))) {
                        unsigned int nxt = cur;
                        nxt = nxt & (~(1<<i)) & (~(1<<(i+1)));
                        nxt = nxt | (1<<(i+2));
                        dp[nxt] = dp[cur] - 1;
                        Q.push(nxt);
                    }
                }
            }
        }
        // Output
        printf("%d\n", Min);
    }
}
#endif // BITMASK

#ifdef BACKTRACKING
int Min;
void Backtracking(char board[], int num)
{
    Min = min(Min, num);
    for (int i = 0; i < 12; ++i) {
        if (board[i] == 'o') {
            if (i>=2 && board[i-1]=='o' && board[i-2]=='-') {
                board[i] = board[i-1] = '-'; board[i-2] = 'o';
                Backtracking(board, num-1);
                board[i] = board[i-1] = 'o'; board[i-2] = '-';
            }
            if (i<=9 && board[i+1]=='o' && board[i+2]=='-') {
                board[i] = board[i+1] = '-'; board[i+2] = 'o';
                Backtracking(board, num-1);
                board[i] = board[i+1] = 'o'; board[i+2] = '-';
            }
        }
    }
}
int main()
{
    int T;
    char line[15];
    scanf("%d", &T);
    while (T--) {
        scanf("%s", line);
        int num = 0;
        for (int i = 0; i < 12; ++i)
            if (line[i] == 'o') ++num;

        Min = 99;
        Backtracking(line, num);

        printf("%d\n", Min);
    }
}
#endif // BACKTRACKING