http://poj.grids.cn/practice/1753/ 关灯游戏的变体 BFS

FlipGameBFS.cpp

/*************************************************************************
Author: logicmd
Created Time: 2012/10/8 20:20:15
File Name: FlipGame.cpp
Description: 引用参数
************************************************************************/

#include <cassert>
#include <iostream>
#include <queue>
#include <set>
#include <cstdio>
#include <utility>
#include <algorithm>
#include <cmath>
#include <bitset>

#define M 4
#define N 4
#define MAX M*N

/*
 * const int M=4;
 * const int N=4;
 * const int MAX=M*N;
 */

using namespace std;

typedef pair<int, int> solution;

int binary_array[MAX];

inline int index_calc(int i, int j)
{
    return i*N+j;
}


void flip_one(int i, int j, bitset<MAX> &bs)
{
    bs.flip(index_calc(i,j));
    if (i-1>-1)
        bs.flip(index_calc(i-1,j));
    if (j-1>-1)
        bs.flip(index_calc(i,j-1));
    if (i+1<M)
        bs.flip(index_calc(i+1,j));
    if (j+1<N)
        bs.flip(index_calc(i,j+1));
}



int trans(bitset<MAX> const &bs)
{
    return (int) bs.to_ulong();
}

void init_binary_array()
{

    for(int i=0; i<MAX; i++)
    {
        bitset<MAX> bs (0);
        flip_one(i/4, i%4, bs);
        binary_array[i] = trans(bs);
        //cout << binary_array[i] << endl;
    }

}


int main()
{
    // 初始化16种关灯的pattern
    init_binary_array();

    // 输入
    int in = 0;
    string str;
    for(int i = 0; i < M; ++i)
    {
        cin >> str;
        int j = 0;
        // 求16个2进制位的和入队
        for(string::iterator its=str.begin(); its<str.end(); its++)
        {
            if(*its=='b')
            {
                in += (1 << (15-i*4-j));
            }
            j++;
        }
    }

    //cout << in << endl;

    // Q用于队列，space用于记录走过的解空间，用于剪枝。
    queue<solution> Q;
    set<int> space;

    solution init (in, 0);
    Q.push(init);
    space.insert(in);

    int result = -1;

    while(Q.size()!=0)
    {
        solution base = Q.front();
        Q.pop();
        for (int i = 0; i < MAX; ++i)
        {
            solution now;

            now.first = base.first ^ binary_array[i];
            now.second = base.second + 1;



            // 未找过
            if(space.find(now.first)==space.end())
            {

                if(now.first == 0x0000 || now.first == 0xffff)
                {
                    result = now.second;
                    break;
                }

                Q.push(now);
                space.insert(now.first);
            }

        }

        if(result != -1)
        {
            break;
        }
    }

    if (result != -1)
    {
        cout << result << endl;
    }
    else
    {
        cout << "Impossible" << endl;
    }


    //system("PAUSE");

    return 0;
}