poj 1222 EXTENDED LIGHTS OUT(位运算+枚举)

http://poj.org/problem?id=1222

题意：给一个确定的5*6放入矩阵。每一个格子都有一个开关和一盏灯，0表示灯没亮，1表示灯亮着。让你输出一个5*6的矩阵ans[i][j],ans[i][j] = 1表示按下开关，ans[i][j] = 0表示不按开关，使最后全部的灯都熄灭。

思路：与http://acm.hdu.edu.cn/showproblem.php?pid=1882类似。在这里找到一种方案输出就可以。但有一个疑惑不解。最后ans[ ][ ]输出的时候每一行里要倒着输出。。。

#include

#include

#include

#include

#include

#include

#define LL long long

#define _LL __int64

using namespace std;

const int INF = 0x3f3f3f3f;

int map[7][7];

int sta[7],tmp[7];

int ans[7][7];

int bit[8] = {1,2,4,8,16,32,64,128};

void solve()

{

for(int i = 0; i < (1<<6); i++)

{

memcpy(tmp,sta,sizeof(sta));

memset(ans,0,sizeof(ans));

for(int j = 0; j < 6; j++)

{

if(bit[j]&i)

{

ans[0][j] = 1;

if(j > 0)

tmp[0] ^= bit[j-1];

if(j < 5)

tmp[0] ^= bit[j+1];

tmp[0] ^= bit[j];

tmp[1] ^= bit[j];

}

}

for(int j = 1; j < 5; j++)

{

for(int k = 0; k < 6; k++)

{

if(bit[k]&tmp[j-1])

{

ans[j][k] = 1;

if(k > 0)

tmp[j] ^= bit[k-1];

if(k < 5)

tmp[j] ^= bit[k+1];

tmp[j] ^= bit[k];

tmp[j+1] ^= bit[k];

}

}

}

if(!tmp[4])

{

for(int i = 0; i < 5; i++)

{

for(int j = 5; j > 0; j--)

printf("%d ",ans[i][j]);

printf("%d\n",ans[i][0]);

}

break;

}

}

}

int main()

{

int test;

scanf("%d",&test);

int item = 1;

while(test--)

{

memset(sta,0,sizeof(sta));

for(int i = 0; i < 5; i++)

{

for(int j = 0; j < 6; j++)

{

scanf("%d",&map[i][j]);

if(map[i][j] == 0)

sta[i] <<= 1;

else sta[i] = (sta[i]<<1)+1;

}

}

printf("PUZZLE #%d\n",item++);

solve();

}

return 0;

}

相关链接