The Pilots Brothers' refrigerator

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

题目来源：The Pilots Brothers' refrigerator
这一题的思路跟flip game相似，但是直接使用stl会TLE，所以重写了位运算和队列部分。

#include <stdio.h>

int visited[65536];
int p[65536][2], head, tail, q[65536];

void push(int b)
{
    q[tail++] = b;
}

int front(void)
{
    return q[head];
}

void pop(void)
{
    head++;
}

int empty(void)
{
    return head == tail;
}

int flip(int b, int pos)
{
    int i, x, y;
    int bb = b;

    x = pos / 4;
    y = pos - x * 4;
    for(i = 0; i < 4; i++)
    {
        bb ^= 1 << (15 - y - i * 4);
        bb ^= 1 << (15 - i - x * 4);
    }
    bb ^= 1 << (15 - pos);

    return bb;
}

void print(int num)
{
    int x, y;

    if(-1 == p[num][0])
        return;

    print(p[num][0]);
    x = p[num][1] / 4;
    y = p[num][1] - x * 4;

    printf("%d %d\n", x + 1, y + 1);
}

int main(void)
{
    char str[5];
    int i, j, step = 0, num, b = 0, bb;

    for(i = 0; i < 4; i++)
    {
        scanf("%s", str);
        for(j = 0; j < 4; j++)
        {
            if('-' == str[j])
                b |= 1 << (15 - i * 4 - j);
        }
    }

    push(b);
    for(i = 0; i < 65536; i++)
    {
        visited[i] = 0;
        p[i][0] = p[i][1] = -1;
    }
    visited[b] = 1;

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

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

            if(!visited[bb])
            {
                p[bb][0] = b;
                p[bb][1] = i;
                visited[bb] = visited[b] + 1;
                push(bb);
            }

            if(65535 == bb)
            {
                step = visited[b];
                num = bb;
                goto done;
            }
        }
    }

done:
    printf("%d\n", step);
    print(num);

    return 0;
}