枚举

时间：2010-06-04 来源：buptstehc

题目来源：Flip Game
白色和黑色分别用0和1表示，这样翻转过程中的每一个状态就可以用一个16bit的二进制数来表示，题目由此转换为求从初始状态到全0或全1状态的最少步数，利用bfs来解决。状态扩展过程中枚举16种翻法，发现新状态就继续扩展，否则舍弃。

#include <stdio.h>
#include <queue>
#include <bitset>
using namespace std;

unsigned long visited[65536];
queue< bitset<16> > q;
int inc[5][2] = {0,0,0,1,0,-1,1,0,-1,0};

bitset<16> flip(bitset<16> b, int pos)
{
    int i, x = pos % 4, y = pos / 4, xx, yy;
    bitset<16> bb = b;

    for(i = 0; i < 5; i++)
    {
        xx = x + inc[i][0];
        yy = y + inc[i][1];
        if((xx >= 0) && (xx <= 3) && (yy >= 0) && (yy <= 3))
            bb.flip(xx + yy * 4);
    }

    return bb;
}

int main(void)
{
    char str[5];
    int i, j, sum;
    unsigned long step = 0;
    bitset<16> b, bb;
    bool flag = false;

    b.reset();
    for(i = 0; i < 4; i++)
    {
        scanf("%s", str);
        for(j = 0; j < 4; j++)
        {
            if('b' == str[j])
                b[15 - i * 4 - j] = 1;
        }
    }
    sum = b.count();
    if((0 == sum) || (16 == sum))
    {
        flag = true;
        goto done;
    }

    q.push(b);
    for(i = 0; i < 65536; i++)
        visited[i] = 0;
    visited[b.to_ulong()] = 1;

    while(!q.empty())
    {
        b = q.front();
        q.pop();

        for(i = 0; i < 16; i++)
        {
            bb = flip(b, i);

            sum = bb.count();
            if((0 == sum) || (16 == sum))
            {
                flag = true;
                step = visited[b.to_ulong()];
                goto done;
            }

            if(!visited[bb.to_ulong()])
            {
                visited[bb.to_ulong()] = visited[b.to_ulong()] + 1;
                q.push(bb);
            }
        }
    }

done:
    if(flag)
        printf("%ld\n", step);
    else
        printf("Impossible\n");

    return 0;
}