poj 1222 EXTENDED LIGHTS OUT

/*
* @Author: Lyucheng
* @Date:   2017-08-05 20:12:23
* @Last Modified by:   Lyucheng
* @Last Modified time: 2017-08-05 21:21:02
*/
/*
 题意：给你一个5*6的01矩阵，每次你可以反转一个元素，并且周围的四个元素跟着反转，让你找出一组解。

 思路：就像状压DP，第一行的状态确定了，接下来的状态就确定了，所以只需要枚举第一行的状态就行了
*/
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>

#define MAXN 10

using namespace std;

int t;
int a[MAXN][MAXN];//初始状态
int b[MAXN][MAXN];//末尾状态
int pos[MAXN][MAXN];//保存每行的状态
const int tol=(1<<6);
bool FLAG;
inline void cal_one(int x,int i){//改变一行的状态
    for(int j=1;j<=6;j++){
        if(( ( 1<<(j-1) ) &x) !=0){//需要变换状态的
            pos[i][j]=1;
            a[i][j]=!a[i][j];
            a[i-1][j]=!a[i-1][j];
            a[i+1][j]=!a[i+1][j];
            a[i][j-1]=!a[i][j-1];
            a[i][j+1]=!a[i][j+1];
        }
    }
}

inline void cal_other(int i){//返回这一行的参数
    for(int j=1;j<=6;j++){
        if(a[i-1][j]==1){//如果上一行有1的话，这行这列必须反转一下
            pos[i][j]=1;
            //翻转
            a[i][j]=!a[i][j];
            a[i-1][j]=!a[i-1][j];
            a[i+1][j]=!a[i+1][j];
            a[i][j-1]=!a[i][j-1];
            a[i][j+1]=!a[i][j+1];
        }
    }
}

void Reset(){
    for(int i=0;i<6;i++){
        for(int j=0;j<7;j++){
            a[i][j]=b[i][j];
            pos[i][j]=0;
        }
    }
}

inline void init(){
    memset(a,0,sizeof a);
    memset(b,0,sizeof b);
}

int main(){
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d",&t);
    for(int ca=1;ca<=t;ca++){
        printf("PUZZLE #%d\n",ca);
        init();
        for(int i=1;i<=5;i++){
            for(int j=1;j<=6;j++){
                scanf("%d",&b[i][j]);
            }
        }
        for(int i=0;i<tol;i++){//枚举第一行的状态
            Reset();//初始化一下a矩阵
            cal_one(i,1);
            for(int j=2;j<=5;j++){//变换剩余行的矩阵
                cal_other(j);
            }
            FLAG=true;
            for(int j=1;j<=6;j++){
                if(a[5][j]==1){
                    FLAG=false;
                    break;
                }
            }
            if(FLAG==true) break;
        }
        for(int i=1;i<=5;i++){
            for(int j=1;j<=6;j++){
                printf(j==1?"%d":" %d",pos[i][j]);
            }
            putchar(‘\n‘);
        }
    }
    return 0;
}