Uva - 10651 - Pebble Solitaire

题意：12个位置，有些有鹅卵石，有些是空的，2个连续的鹅卵石，

如果其左边连着的那个是空的，那么第二个鹅卵石可移动到那个空的位置上，并移除第1个鹅卵石；

如果其右边连着的那个是空的，那么第一个鹅卵石可移动到那个空的位置上，并移除第2个鹅卵石。

问最后最少可以剩下多少个鹅卵石。

题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=114&problem=1592

——>>

状态压缩

判断其若未是不可移动的最终态，则继续进行dp，怎么判？12个位置3个3个扫一次即可。

#include <iostream>using namespace std;int minn;
int dp(int x)
{int i, cnt = 0;for(i = 1; i <= 10; i++)if(((x&(1<<(i-1))) && (x&(1<<i)) && !(x&(1<<(i+1)))) || (!(x&(1<<(i-1))) && (x&(1<<i)) && (x&(1<<(i+1))))){x ^= (1<<(i-1));x ^= (1<<i);x ^= (1<<(i+1));int temp = dp(x);if(temp < minn) minn = temp;        //更新最小值x ^= (1<<(i-1));        //回溯x ^= (1<<i);        //回溯x ^= (1<<(i+1));        //回溯cnt++;}if(cnt == 0)        //判断是否为最终态{int ans = 0;for(i = 0; i < 12; i++)if(x&(1<<i)) ans++;if(ans < minn) minn = ans;}return minn;
}
int main()
{char s[15];int T, i;cin>>T;while(T--){cin>>s;int a = 0;for(i = 0; i < 12; i++)if(s[i] == 'o') a = a^(1<<i);minn = (1<<30);cout<<dp(a)<<endl;}return 0;
}