题意就不多说了,就是问那种方式可以把所有的灯都关掉.
直接一波位运算,因为是6列,所以一个char型就可以存下来了.
链接
poj --- 1222
主要思想就是状态压缩,复杂度是2^n次方,n为列数.
AC代码如下:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
char orilight[10]; //初始灯的状态.
char result[10]; //结果的操作数.
char light[10]; //中间操作时灯的状态.
int t;
int Getbit(char c,int i)
{//取字符c的第i个bit.
return (c >> i) & 1;
}
void setbit(char & c,int i,int v) //这样引用的话,形参改变对应实参也会改变.
{//把c的第i位设置成v.
if(v ){
c |= (1 << i); //是不能改的.不要只看到这一位,他改变是要求改变这一位,并且其他位不变.
} //只用这样才能做到的！.
else
c &= ~(1 << i);
}
void flipbit(char & c ,int i)
{ //把c的第i位翻转.(1 翻为0 , 0 翻为 1).
c ^= (1 << i) ;
}
void print(int t,char result[])
{
cout << "PULLZE #" << t << endl;
for(int i=0;i<5;i++){
for(int j=0;j<6;j++){
cout << Getbit(result[i],j);
if(j<5)
cout << " " ;
else
cout << endl;
}
}
}
int main()
{
int T;
cin >> T;
for(int t=1;t<=T;t++){
for(int i=0;i<5;i++){
for(int j=0;j<6;j++){
int k;
cin >> k;
setbit(orilight[i],j,k);
}
}
/*for(int i=0;i<5;i++){
for(int j=0;j<6;j++){
int k;
k=Getbit(orilight[i],j);
cout << k << " " ;
}
cout << endl;
}*/
for(int n=0;n<64;n++){
memcpy(light,orilight,sizeof(light));
int switchs=n; //开关的状态存在switchs中,
for(int i=0;i<5;i++){
result[i]=switchs;
for(int j=0;j<6;j++){ // 对同一行(即第i行)的灯进行处理.
if(Getbit(switchs,j)){
if(j>0)
flipbit(light[i],j-1);
flipbit(light[i],j);
if(j < 5)
flipbit(light[i],j+1);
}
}
if(i < 4) //因为下一行的操作是根据上一行的状态进行的操作,所以不用再去管上一行.
light[i+1] ^= switchs; //影响第i+1行的灯的状态.
switchs = light[i]; //因为下一行的操作是要根据上一行来进行的,所以需要在把switch再来赋值一波.
//因为上一行灯的状态就是下一行的操作状态.
}
if(light[4] == 0){
print(t,result);
break;
}
}
}
}
与上面那道题的一样的,只是这道题的范围没定而已.
poj --- 3279
链接
AC代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int m,n;
int tile[20];
int ans[20];
int result[20];
int Getbit(int x,int i) //这些子函数的功能与上面那个一样.
{
return (x >> i) & 1 ;
}
void Setbit(int & x,int i,int v)
{
if( v ){
x |= (1 << i) ;
}
else
x &= ~(1 << i);
}
void Flipbit(int & x,int i)
{
x ^= (1 << i);
}
void Outresult(int result[])
{
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cout << Getbit(result[i],j);
if(j < m-1)
cout << " ";
else
cout << endl;
}
}
}
int qpow(int m,int n) //快速幂,可有可无.
{
int res=1;
while(n){
if(n&1) res *= m;
m *= m;
n >>= 1;
}
return res;
}
int main()
{
cin >> n >> m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int k;
cin >> k;
Setbit(tile[i],j,k);
}
}
/*for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int k = Getbit(tile[i],j);
cout << k << " ";
}
cout << endl;
}*/
int p= qpow(2,m); //快速幂而已,也可以用库函数pow,但是注意下精度就是了.
//cout << p<< endl;
for(int t=0;t<p;t++){
int sw=t;
memcpy(ans,tile,sizeof(ans)); // 是把后面那个数组的内容赋给前面那个数组.
for(int i=0;i<n;i++){
result[i]=sw;
for(int j=0;j<m;j++){
if(Getbit(sw,j)){
if(j>0 )
Flipbit(ans[i],j-1);
Flipbit(ans[i],j);
if(j < m-1)
Flipbit(ans[i],j+1);
}
}
if(i<n-1)
ans[i+1] ^= sw;
sw = ans[i];
}
if(ans[n-1] == 0){
Outresult(result);
return 0;
}
}
cout << "IMPOSSIBLE" << endl;
}
