POJ 1753（1）

按照训练计划，每天尽量往后刷吧

题意：一个4x4的棋盘，有黑有白，当这个棋盘上所有的棋子都是白或者都是黑，就结束了；每次翻转一个棋子，那么他的上下左右方向（如果不越界）都要翻转，即黑->白，白->黑；

solve:把这十六个棋子转换成一个十六位的二进制数，因为二进制数只有0和1两种状态，所以，枚举一遍即可。先转换成二进制数；广搜：先将当前状态的每一个棋子翻转一遍看是否能够满足要求，如果不满足进入队列。用一个step数组记录步数。

代码是网上大牛的：

#include <iostream>
#include <queue>

using namespace std;

int step[65535];  //记录步骤
bool flag[65535];  //防止重复搜索

int qState[65535]; //搜索的状态，正好可以用一个16位的无符号短整形表示
int rear = 0; //队列尾指针
int top = 0; //队列头指针

///初始化：读入棋盘初始状态并把它转化为整数存入队列头，黑的位为1白的为0
void Init()
{
    int temp = 0;
    char c;
    for(int i=0; i < 4; i++)
        for(int j = 0; j < 4; j++)
        {
            cin>>c;
            if('b' == c)
                temp |= (1<<(i*4+j));
        }
    qState[rear++] = temp;
    flag[temp]  = true;
}

///翻转一个棋子并按规则对齐周围棋子附加影响
unsigned short move(unsigned short state, int i)
{
    int temp=0;
    temp = (1<<i);
    if((i+1)%4 != 0) //右，且不在最右边
        temp |= (1<<(i+1));
    if(i%4 != 0) //左，且不在最左边
        temp |= (1<<(i-1));
    if(i+4 < 16) //下
        temp |= (1<<(i+4));
    if(i-4 >= 0) //上
        temp |= (1<<(i-4));
    return (state ^ temp);
}

//广度优先搜索，从队列中循环取出状态，并把翻转16次（即所有情况），一旦发现满足要求的立即停止，否则加入队列
bool BFS()
{
    while(rear > top)
    {
        int state = qState[top++];
        //qState.pop();
        for(int i=0; i < 16; i++)
        {
            int temp;
            temp = move(state,i);
            if(0 == state || 65535 == state)
            {
                cout<<step[state];
                return true;
            }
            else if(!flag[temp]) //防止重复搜索
            {
                //qState.push(temp);
                qState[rear++] = temp;
                flag[temp] = true;
                step[temp] = step[state]+1;
            }
        }
    }
    return false;
}

int main(void)
{
    Init();
    if(!BFS()) cout<<"Impossible";
    char c;
    cin>>c;
}