[POJ] 1753 Flip Game.cpp

#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;
}