http://isaac.lsu.edu/uva/106//10651.html
Output
跳棋，例如"oo-"表示第一和第二個位置有棋子，第三個位置是空的，因此第一個位置的棋子可以跳過第二個位置的棋子並取走第二個位置的棋子，變成"--o"。題目給定一個12個位置的棋盤，問經過不斷跳棋後，剩下最少棋子的數量。
想法：
想到兩種方式：bitmask+bfs或是backtracking，兩種方法其實差不多，都是把所有的情況枚舉，找出最小値。第一種方法為0.009s，第二種為0.012s，時間相差不大，寫backtracking是較簡單的。
X.
http://www.voidcn.com/article/p-bvcvddwb-ge.html
状态压缩DP，用一个int的当前位有1表示当前位有珠子。
https://ageneidy.wordpress.com/2014/08/04/uva-10651-pebble-solitaire/
X. BFS
http://andrew-algorithm.blogspot.com/2014/11/uva-problem-10651-pebble-solitaire.html
https://www.cnblogs.com/yuzhaoxin/archive/2012/04/06/2435272.html
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);
}
X.
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.
5
---oo-------
-o--o-oo----
-o----ooo---
oooooooooooo
oooooooooo-o
|
1
2
3
12
1
|
int GetMin(int board)
{
int &best = saved[board];
if (best == -1)
{
best = GetNumPebbles(board);
// Shift to the left
for (int i = 2; i < NumPebbles; ++i)
{
if (HasPebble(i, board) && HasPebble(i - 1, board) && !HasPebble(i - 2, board))
{
int newBoard = board ^ (1 << i) ^ (1 << (i - 1)) ^ (1 << (i - 2));
best = min(best, GetMin(newBoard));
}
}
// Shift to the right
for (int i = NumPebbles - 3; i >= 0; --i)
{
if (HasPebble(i, board) && HasPebble(i + 1, board) && !HasPebble(i + 2, board))
{
int newBoard = board ^ (1 << i) ^ (1 << (i + 1)) ^ (1 << (i + 2));
best = min(best, GetMin(newBoard));
}
}
}
return best;
}
int encoded = 0;
for (int i = 0; i < NumPebbles; ++i)
if (board[i] == 'o')
encoded |= (1 << i);
cout << GetMin(encoded) << '\n';
This problem is a particularization of the pebble game. In this problem you have a set of marbles and play according to some established rules. Suppose there two marbles: one at position i and the other at position i+1. You can eliminate the marble at position i+1 by hopping the marble at position i over it. Hopping marble means moving the one that is in position i to position i+2 (i+1 is the position of the other marble). In this problem you are given a description of this game consisting of 12 spaces and some of them are filled with marbles. You should determine the minimum number of marbles that will be left after a series of movements of the marbles. A marble can hop either left or right, if there is another adjacent at marble i-1 or i+1, respectively.
Analysis:
Suppose there is a marble at position i and another marble at position i+1. Also suppose that positions i-1 and i+2 are valid positions. In this case, there are two possible movements, every movement will left one marble in the board. You can either move the marble located at i to position i+2, thus, eliminating the marble at position i+1, or you can move the marble at position i+1 to i-1, thus, eliminating the marble at position i.
Suppose there is a marble at position i and another marble at position i+1. Also suppose that positions i-1 and i+2 are valid positions. In this case, there are two possible movements, every movement will left one marble in the board. You can either move the marble located at i to position i+2, thus, eliminating the marble at position i+1, or you can move the marble at position i+1 to i-1, thus, eliminating the marble at position i.
Solution:
The solutions consist on using backtracking to solve the movement of the marbles. You should check for every marble, first if it can be moved. If a marble can be moved to both directions (left and right) try both possibilities, generating a new scenario for every move. That means, after performing one move (left or right), recurse so that you will get an answer based on that decision. Repeat this process for all the marbles that can be moved, and minimize the value at every ending state. i.e An ending state means that there aren’t anymore moves to perform.
http://programming-study-notes.blogspot.com/2014/05/uva-10651-pebble-solitaire.htmlThe solutions consist on using backtracking to solve the movement of the marbles. You should check for every marble, first if it can be moved. If a marble can be moved to both directions (left and right) try both possibilities, generating a new scenario for every move. That means, after performing one move (left or right), recurse so that you will get an answer based on that decision. Repeat this process for all the marbles that can be moved, and minimize the value at every ending state. i.e An ending state means that there aren’t anymore moves to perform.
跳棋，例如"oo-"表示第一和第二個位置有棋子，第三個位置是空的，因此第一個位置的棋子可以跳過第二個位置的棋子並取走第二個位置的棋子，變成"--o"。題目給定一個12個位置的棋盤，問經過不斷跳棋後，剩下最少棋子的數量。
想法：
想到兩種方式：bitmask+bfs或是backtracking，兩種方法其實差不多，都是把所有的情況枚舉，找出最小値。第一種方法為0.009s，第二種為0.012s，時間相差不大，寫backtracking是較簡單的。
X.
http://www.voidcn.com/article/p-bvcvddwb-ge.html
状态压缩DP，用一个int的当前位有1表示当前位有珠子。
https://ageneidy.wordpress.com/2014/08/04/uva-10651-pebble-solitaire/
static int[] masks = new int[1 << 12]; static int setbit(int mask, int idx, int val) { return (val == 1) ? (mask | (1 << idx)) : (mask & ~(1 << idx)); } static boolean getBit(int mask, int idx) { return ((mask >> idx) & 1) == 1; } static int cntBit(int mask) { int cnt = 0; while (mask > 0) { if (mask % 2 == 1) cnt++; mask /= 2; } return cnt; } private static int best(int mask) { // TODO Auto-generated method stub if (masks[mask] != -1) return masks[mask]; masks[mask] = 0; for (int i = 0; i < 10; i++) { if (getBit(mask, i) && getBit(mask, i + 1) && !getBit(mask, i + 2)) { int tmask = mask; tmask = setbit(tmask, i, 0); tmask = setbit(tmask, i + 1, 0); tmask = setbit(tmask, i + 2, 1); masks[mask] = Math.max(masks[mask], 1 + best(tmask)); } if (!getBit(mask, i) && getBit(mask, i + 1) && getBit(mask, i + 2)) { int tmask = mask; tmask = setbit(tmask, i, 1); tmask = setbit(tmask, i + 1, 0); tmask = setbit(tmask, i + 2, 0); masks[mask] = Math.max(masks[mask], 1 + best(tmask)); } } return masks[mask]; }X. BFS
http://andrew-algorithm.blogspot.com/2014/11/uva-problem-10651-pebble-solitaire.html
https://www.cnblogs.com/yuzhaoxin/archive/2012/04/06/2435272.html
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);
}
int dp(int),map[N],vis[N];
int main()
{
int n;
char str[100];
scanf("%d",&n);
getchar();
while(n--)
{
memset(map,0,sizeof(map));
memset(vis,0,sizeof(vis));
gets(str);
int len=strlen(str),num=0;
for(int i=0;i<len;i++)
{
if(str[i]=='o') num^=1<<(i);
}
printf("%d\n",dp(num));
}
return 0;
}
int dp(int x)
{
if(vis[x]) return map[x];
else
{
int imin=15;
bool flag=true;
for(int i=0;i<12;i++)
{
if(x&(1<<(i))&&x&(1<<(i+1)))
{
if(i>0&&!(x&(1<<(i-1)))) {imin=min(imin,dp(x^(1<<(i-1)^(1<<i)^(1<<(i+1)))));flag=false;}
if(i+2<12&&!(x&(1<<(i+2)))) {imin=min(imin,dp(x^(1<<i)^(1<<(i+1)^(1<<(i+2)))));flag=false;}
}
}
if(flag)
{
int temp=0;
for(int i=0;i<12;i++)
{
if(x&(1<<i)) temp++;
}
vis[x]=1;
map[x]=temp;
return temp;
}
vis[x]=1;
map[x]=imin;
return imin;
}
map<string,int>d;
string str,t;
int n,ans;
int dp(string s)
{
if(d[s]>0) return d[s];
d[s]=1;
for(int i=0;i<10;i++)
{
if(s[i]=='o'&&s[i+1]=='o'&&s[i+2]=='-')
{
t=s;
t[i]=t[i+1]='-';
t[i+2]='o';
d[s]=max(d[s],dp(t)+1);
}
if(s[i]=='-'&&s[i+1]=='o'&&s[i+2]=='o')
{
t=s;
t[i]='o';
t[i+1]=t[i+2]='-';
d[s]=max(d[s],dp(t)+1);
}
}
return d[s];
}
X.
把12个棋位的有无棋子整体看作一个状态，然后宽搜就可以了
DP题，状态总量为2^12，其实可以用对称性减少一半状态数。
