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

FlipGame.cpp

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

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