uva 10651 Pebble Solitaire （BFS）

uva 10651 Pebble Solitaire

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

5

—oo——-

-o–o-oo—-

-o—-ooo—

oooooooooooo

oooooooooo-o

1

2

3

12

1

題目大意：給出一種棋子（其實是鵝卵石，看成是棋子）排列的情況，‘o’代表當前位置有棋子，‘-’代表空。當出現“oo-”或者“-oo”的情況時，棋子可以發生跳轉，棋子可以以它相鄰的棋子為支撐點跳到支撐點另一邊的空位上，作為支撐點的棋子會消失。問。在經過跳轉後最少剩下的棋子數。

解題思路：用BFS或者DFS都能做。

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
char s[13];
int first, last, Min, vis[10005];
struct queue{
    char num[13];
    int hash() {
        int sum = 0;
        for (int i = 0; i < 12; i++) {
            if (num[i] == 'o') {
                sum += 1 << (12 - i); 
            }
        }
        return sum;
    }
};
queue q[100005];
void BFS() {
    char temp[13];
    while (first < last) {
        int cnt = 0;
        strcpy(temp, q[first].num);
        for (int i = 0; i < 12; i++) {
            if (temp[i] == 'o') {
                cnt++;
                if (i >= 2) {
                    if (temp[i - 1] == 'o' && temp[i - 2] == '-') {
                        strcpy(q[last].num, temp);
                        q[last].num[i] = q[last].num[i - 1] = '-';
                        q[last].num[i - 2] = 'o';
                        if (!vis[q[last].hash()]) {
                            vis[q[last].hash()] = 1;
                            last++;
                        }
                    }
                }
                if (i <= 9) {
                    if (temp[i + 1] == 'o' && temp[i + 2] == '-') {
                        strcpy(q[last].num, temp);
                        q[last].num[i] = q[last].num[i + 1] = '-';
                        q[last].num[i + 2] = 'o';
                        if (!vis[q[last].hash()]) {
                            vis[q[last].hash()] = 1;
                            last++;
                        }
                    }
                }
            }
        }
        if (cnt < Min) Min = cnt;
        first++;
    }
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        memset(vis, 0, sizeof(vis));
        scanf("%s", s);
        first = last = 1;
        strcpy(q[first].num, s);            
        vis[q[first].hash()] = 1;
        last++;
        Min = 13;
        BFS();
        printf("%d\n", Min);
    }
    return 0;
}