poj 1753 Flip Game(bfs+枚举)

解题思路

题意：

       给出一盘棋，要通过翻转将此变成全都是黑色或全都是白色，翻动某个棋子时，它上下左右四个方向的棋子全都要翻，问最少要翻几次。

 

思路：

       因为是4x4的棋盘，而且每个棋子只有2种状态(可以用0和1表示)，所以整个棋盘的状态可以用一个整数stat（只需16位）来表示。

       然后把每个状态都通过翻十六次来枚举一遍，直到某种状态满足要求(当stat==0 全白 或者stat==0xffff全黑)；或者所有状态都试过不行输出“impossible”。

 

   如此来存储输入的原始状态：

    Unsigned int stat;
    stat <<= 1;
    for(i=0; i<4; i++, getchar())
       for(j=0; j<4; j++)
       {
           a[i][j] = getchar();
           stat <<= 1; 
           a[i][j] == 'b' ? stat++: 1;
       }


先判断一下是否已经全白或全黑了。不是的话继续：

建一个队列，存放原始状态和每次翻转后新的状态。然后从队列取出来要枚举翻转的状态，然后挨个翻一遍，每翻一个棋子就判断下是否满足要求了，是的话直接输出结果，否则，把新的状态放进队列里，此种翻转次数增一。16个棋子都翻完了再去下一个状态。 过程是如此的：

 

    que[++rear] = stat;
    flag[stat] = 1;
    step[stat] = 0;
    while(rear > top)
    {
        stat = que[++top];
        for(i=0; i<16; i++)
        {
            temp = move(stat, i);
            if(temp == 0 || temp == 0xffff)
            {
                printf("%d\n", step[stat]+1);
                return 0;
            }
            else if(flag[temp] != 1)
            {
                que[++rear] = temp;
                step[temp] = step[stat]+1;
                flag[temp] = 1;
            }
        }
    }


对于某个棋子，我的翻转方法是如此的：

 

unsigned int offset[4] = {0x8c80, 0x4e40, 0x2720, 0x1310};
unsigned int move(unsigned int stat, int i)
{
    if(i >= 4)
        stat ^= ((offset[i%4] >> ((i/4-1)*4)) & 0x0000ffff);
    else
        stat ^= ((offset[i] << 4) & 0x0000ffff);
    return stat;
}


因为要改变某一位的状态，只要用1来跟那一位异或运算。

然后我发现：第一行的四个需要的是：

1100   1110   0111   0011

1000   0100   0010   0001

0000   0000   0000   0000

0000   0000   0000   0000

分别用0xc800, 0xe400, 0x7200, 0x3100来异或。后面的同理找出规律。

第二行用0x8c80, 0x4e40, 0x2720, 0x1310

第三行用0x08c8, 0x04e4, 0x0272, 0x0131

第四行用0x008c, 0x004e, 0x0027, 0x0013

规律很明显吧，然后做一点点简单的运算就ok了。

 

ps:好久没上poj做题了，感觉都快忘了，昨天做了下hdu的情人节专场，唉...失败啊。想了很久，感觉算法还是不能忘啊，终于下定决心，要把寒假的剩下的时间献给ACM了。 

解题报告继续会写，不过不在博客里贴完整的代码了。

 

呦西！ 加油小c！