UVa 10651 Pebble Solitaire

題意：
    跳棋，例如"oo-"表示第一和第二個位置有棋子，第三個位置是空的，因此第一個位置的棋子可以跳過第二個位置的棋子並取走第二個位置的棋子，變成"--o"。題目給定一個12個位置的棋盤，問經過不斷跳棋後，剩下最少棋子的數量。

想法：
    想到兩種方式：bitmask+bfs或是backtracking，兩種方法其實差不多，都是把所有的情況枚舉，找出最小値。第一種方法為0.009s，第二種為0.012s，時間相差不大，寫backtracking是較簡單的。

	#include <cstdio>
	#include <queue>
	using namespace std;
	#define BACKTRACKING
	#ifdef BITMASK
	int main()
	{
	int T;
	char line[15];
	scanf("%d", &T);
	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);
	}
	}
	#endif // BITMASK
	#ifdef BACKTRACKING
	int Min;
	void Backtracking(char board[], int num)
	{
	Min = min(Min, num);
	for (int i = 0; i < 12; ++i) {
	if (board[i] == 'o') {
	if (i>=2 && board[i-1]=='o' && board[i-2]=='-') {
	board[i] = board[i-1] = '-'; board[i-2] = 'o';
	Backtracking(board, num-1);
	board[i] = board[i-1] = 'o'; board[i-2] = '-';
	}
	if (i<=9 && board[i+1]=='o' && board[i+2]=='-') {
	board[i] = board[i+1] = '-'; board[i+2] = 'o';
	Backtracking(board, num-1);
	board[i] = board[i+1] = 'o'; board[i+2] = '-';
	}
	}
	}
	}
	int main()
	{
	int T;
	char line[15];
	scanf("%d", &T);
	while (T--) {
	scanf("%s", line);
	int num = 0;
	for (int i = 0; i < 12; ++i)
	if (line[i] == 'o') ++num;
	Min = 99;
	Backtracking(line, num);
	printf("%d\n", Min);
	}
	}
	#endif // BACKTRACKING

view raw [UVa] 10651 Pebble Solitaire.cpp hosted with ❤ by GitHub