POJ ---- 1222 (强化一波位运算) 和 POJ --- 3279

题意就不多说了,就是问那种方式可以把所有的灯都关掉.
直接一波位运算,因为是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;
}