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

—oo——-

-o–o-oo—-

-o—-ooo—

oooooooooooo

oooooooooo-o

题目大意：给出一种棋子（其实是鹅卵石，看成是棋子）排列的情况，‘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; }

uva 10651 Pebble Solitaire （BFS）

uva 10651 Pebble Solitaire

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