POJ 1753 Flip Game

想法：
    Bit運算，16位來表示棋盤的情況，16個0表示全白，16個1表示全黑。用BFS演算法，從一開始的情況開始出發，直到變成全白或全黑為止，或是無法變成全白或全黑。

	#include <cstdio>
	#include <queue>
	#include <algorithm>
	int dp[1<<16+10] = {0};
	const unsigned int Full_Black = (1<<16)-1;
	const unsigned int Full_White = 0;
	int bfs(unsigned int bit);
	unsigned int toggle(unsigned int bit, int pos);
	int main()
	{
	unsigned int bit = 0;
	char line[5];
	for (int i = 0; i < 4; ++i) {
	scanf("%s", line);
	for (int j = 0; j < 4; ++j) {
	bit <<= 1;
	if (line[j] == 'b') bit |= 1;
	}
	}
	if (bit == Full_Black || bit == Full_White) puts("0");
	else {
	int ans = bfs(bit);
	if (ans == -1) puts("Impossible");
	else printf("%d\n", ans);
	}
	}
	int bfs(unsigned int start_bit)
	{
	std::queue<unsigned int> Q;
	Q.push(start_bit);
	while (!Q.empty()) {
	unsigned int bit = Q.front();
	Q.pop();
	for (int i = 0; i < 16; ++i) {
	unsigned int toggled_bit = toggle(bit, i);
	if (!dp[toggled_bit]) {
	dp[toggled_bit] = dp[bit] + 1;
	if (toggled_bit == Full_Black || toggled_bit == Full_White)
	return dp[toggled_bit];
	Q.push(toggled_bit);
	}
	}
	}
	return -1;
	}
	unsigned int toggle(unsigned int bit, int pos)
	{
	bit ^= (1 << pos); // central
	if (pos-4 >= 0) bit ^= (1 << (pos-4)); // up
	if (pos+4 < 16) bit ^= (1 << (pos+4)); // down
	if (pos%4 >= 1) bit ^= (1 << (pos-1)); // left
	if (pos%4 <= 2) bit ^= (1 << (pos+1)); // right
	return bit;
	}

view raw [POJ] 1753 Flip Game.cpp hosted with ❤ by GitHub