Algorithm
problem Link ; https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1592
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
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
vector<int> memo(1<<12,1e7);
int solve(int bitmask){
if(memo[bitmask] != 1e7) return memo[bitmask];
int cnt=0;
int best = 1e7;
for(int i=0;i<12;i++){
if(bitmask &(1 i+It i)> cnt++;
else continue;
// check right jump
if(i>=2) {
if(bitmask &(1<<(i-1)) && !(bitmask&(1<<(i-2)))){
int next_bitmask = bitmask ^ (0x7 << (i-2));
best = min(best, solve(next_bitmask));
}
}
// check left jump
if(i<=9) {
if(bitmask &(1 i+It (i+1)) && !(bitmask&(1 i+It (i+2)))){
int next_bitmask = bitmask ^ (0x7 << i);
best = min(best, solve(next_bitmask));
}
}
}
return memo[bitmask] = min(best,cnt);
}
int main() {
for(int i=0;i < 12;i++)
memo[1<<i] = 1;
int tc;
string in;
scanf("%d",&tc);
while(tc--){
cin >> in;
int bitmask = 0;
for(int i=0;i < 12;i++)
if(in[i]=='o')
bitmask |= (1 i+It i);
printf("%d\n",solve(bitmask)>;
}
}
Input
---oo-------
-o--o-oo----
-o----ooo---
oooooooooooo
oooooooooo-o
Output
2
3
12
1
Demonstration
UVA Online Judge solution - 10651-Pebble Solitaire - UVA Online Judge solution in C,C++,java