关灯游戏（老POJ1222，新224）

EXTENDED_LIGHTS_OUT.cpp

/*************************************************************************
Author: logicmd
Created Time: 2012/10/8 20:20:15
File Name: EXTENDED_LIGHTS_OUT.cpp
Description: 搜索时，注意保护现场，传数组指针进来先copy一份
************************************************************************/

#include <cassert>
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <string>
#include <utility>
#include <algorithm>
#include <cmath>

#define M 5
#define N 6

using namespace std;

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

void switch_bit(int &i)
{
    if(i == 0)
        i = 1;
    else
        i = 0;
}

void switch_one(int i, int j, int *in_mat)
{
    switch_bit(in_mat[index_calc(i,j)]);
    if (i-1>-1)
        switch_bit(in_mat[index_calc(i-1,j)]);
    if (j-1>-1)
        switch_bit(in_mat[index_calc(i,j-1)]);
    if (i+1<M)
        switch_bit(in_mat[index_calc(i+1,j)]);
    if (j+1<N)
        switch_bit(in_mat[index_calc(i,j+1)]);
}

bool downward(int *l1, int *in_mat, int *out_mat)
{
    bool flag = false;

    int in_copy[M*N];
    copy(in_mat, in_mat+M*N, in_copy);
    // init
    for(int j=0; j<N; j++)
    {
        if (l1[j]==1)
        {
            switch_one(0,j,in_copy);
        }

        out_mat[index_calc(0,j)]=l1[j];
    }

    // downward
    for(int i=0; i<M-1; i++)
    {
        for(int j=0; j<N; j++)
        {
            if(in_copy[index_calc(i,j)]==1)
            {
                switch_one(i+1,j,in_copy);
                out_mat[index_calc(i+1,j)]=1;
            }
            else
            {
                out_mat[index_calc(i+1,j)]=0;
            }
        }
    }

    // check
    for(int j=0; j<N; j++)
    {
        if(in_copy[index_calc(M-1,j)]==0)
        {
            flag = flag || false;
        }
        else
        {
            flag = flag || true;
            break;
        }
    }

    return !flag;

}

// 100100 -> {1, 0, 0, 1, 0, 0}
void trans(int n, int *array)
{
    for(int i=0; i<N; i++)
    {
        array[i] = (n >> (N-1-i)) % 2;
    }

}

// enumerate all l1 and downward
bool solve(int *in_mat, int *out_mat)
{
    int l1[N];
    int out_copy[N*M];
    for(int n=0; n<pow(2,N); n++)
    {
        trans(n, l1);
        if (downward(l1, in_mat, out_copy))
        {
            copy(out_copy, out_copy+M*N, out_mat);
            return true;
        }

    }
    return false;
}



int main()
{
    int n;

    cin >> n;
    int **in = new int * [n];
    int **out = new int * [n];

    for(int i=0; i<n; i++)
    {
        in[i] = new int [30];
        out[i] = new int [30];
    }

    for(int i=0; i<n; i++)
    {
        for(int j=0; j<M*N; j++)
        {
            cin >> in[i][j];
        }

    }

    // switch_one(0,0,in[0]);
    // switch_one(1,4,in[0]);
    // switch_one(2,3,in[1]);

    // int l1[6]={1,0,1,0,0,1};
    // cout << endl << downward(l1,in[0],out[0]);

    // int l2[6]={1,0,0,1,1,1};
    // cout << endl << downward(l2,in[1],out[1]);

    for(int i=0; i<n; i++)
    {
        if(solve(in[i], out[i])) {
            cout << "PUZZLE #" << i+1 <<endl;
            for(int j=0; j<M; j++)
            {
                for(int k=0; k<N; k++)
                {
                    cout << out[i][index_calc(j,k)] << " ";
                }
                cout << endl;
            }
        }
    }
    system("PAUSE");

    return 0;
}

FlipGame.cpp

/*************************************************************************
Author: logicmd
Created Time: 2012/10/8 20:20:15
File Name: FlipGame.cpp
Description: http://poj.grids.cn/practice/1753/ 关灯游戏的变体
************************************************************************/

#include <cassert>
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <string>
#include <utility>
#include <algorithm>
#include <cmath>

#define M 4
#define N 4
#define MAX_COUNT M*N+1

using namespace std;

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

void switch_bit(int &i)
{
    if(i == 0)
        i = 1;
    else
        i = 0;
}

void switch_one(int i, int j, int *in_mat)
{
    switch_bit(in_mat[index_calc(i,j)]);
    if (i-1>-1)
        switch_bit(in_mat[index_calc(i-1,j)]);
    if (j-1>-1)
        switch_bit(in_mat[index_calc(i,j-1)]);
    if (i+1<M)
        switch_bit(in_mat[index_calc(i+1,j)]);
    if (j+1<N)
        switch_bit(in_mat[index_calc(i,j+1)]);
}

bool downward(int *l1, int *in_mat, int &count)
{
    count = 0;
    bool flag = false;

    int in_copy[M*N];
    copy(in_mat, in_mat+M*N, in_copy);
    // init
    for(int j=0; j<N; j++)
    {
        if (l1[j]==1)
        {
            switch_one(0,j,in_copy);
            count++;
        }
    }

    // downward
    for(int i=0; i<M-1; i++)
    {
        for(int j=0; j<N; j++)
        {
            if(in_copy[index_calc(i,j)]==1)
            {
                switch_one(i+1,j,in_copy);
                count++;
            }
        }
    }

    // check
    for(int j=0; j<N; j++)
    {
        if(in_copy[index_calc(M-1,j)]==0)
        {
            flag = flag || false;
        }
        else
        {
            flag = flag || true;
            break;
        }
    }

    return !flag;

}

// 100100 -> {1, 0, 0, 1, 0, 0}
void trans(int n, int *array)
{
    for(int i=0; i<N; i++)
    {
        array[i] = (n >> (N-1-i)) % 2;
    }
}

// enumerate all l1 and downward
int solve(int *in_mat)
{
    int l1[N];
    int out_copy[N*M];
    int count;
    int min_count = MAX_COUNT+1;
    for(int n=0; n<pow(2,N); n++)
    {
        trans(n, l1);
        if (downward(l1, in_mat, count))
        {
            if(count < min_count)
            {
                min_count = count;
            }
        }

    }
    return min_count;
}



int main()
{
    int mat[M*N];
    int mat_mirror[M*N];
    char x;
    for(int i=0; i<M*N; i++)
    {
        cin >> x;
        int xx;
        if(x=='b')
            xx = 0;
        else
            xx = 1;

        mat[i] = xx;
        mat_mirror[i] = 1-xx;
    }

    //cout << solve(mat) << '\t' << solve(mat_mirror);
    int count = min(solve(mat), solve(mat_mirror));
    if (count > MAX_COUNT)
        cout << "Impossible" << endl;
    else
        cout << count;

    //system("PAUSE");

    return 0;
}

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;
}