POJ 1222 优化穷举位运算

终于有时间自己写一遍了，然后本菜鸡昨天一整夜都在debug……多亏XHL发现了我的数组越界……太艰难了

思路：穷举第一行，因为完成了一行的操作以后，要关掉第一行的灯，只能从第二行下手，也就是说，第二行的操作和第一行的状态相同，依此类推。最后检查最后一行，如果关好了，就退出穷举循环，输出结果。

菜鸡代码：

#include <iostream>
#include <cstring>
using namespace std;
int a[5][6],b[5][6],ans[5][6];
void SwapLight(int i,int j) {
    a[i][j]=!a[i][j];//自己
    if(i) a[i-1][j]=!a[i-1][j];//上
    if(j) a[i][j-1]=!a[i][j-1];//左
    if(i!=4) a[i+1][j]=!a[i+1][j];//下
    if(j!=5) a[i][j+1]=!a[i][j+1];//右
}
void SwapLine(int line) {
    for(int i=0; i<6; i++)
        if(ans[line][i])SwapLight(line,i);
}
bool Check() {//只需要检查最后一行
    for(int j=0; j<6; j++)
        if(a[4][j])return 0;
    return 1;
}
void Geta(int k) {//获取第一行的操作
    for(int i=0; i<6; i++) {
        ans[0][i]=(k>>i)&1;
    }
}
void Solve() {//优化穷举
    for(int k=0; k<64; k++) {
        memcpy(a,b,sizeof(b));
        memset(ans,0,sizeof(ans));
        Geta(k);
        for(int i=1; i<5; i++) {
            SwapLine(i-1);
            for(int j=0; j<6; j++) {
                if(a[i-1][j]) ans[i][j]=1;
            }
        }
        SwapLine(4);
        if(Check()) return;
    }
    cout<<"ERROR"<<endl;
}
int main() {
    int t;
    cin>>t;
    for(int PU=1; PU<=t; PU++) {
        for(int i=0; i<5; i++)
            for(int j=0; j<6; j++)
                cin>>b[i][j];
        Solve();
        cout<<"PUZZLE #"<<PU<<endl;
        for(int i=0; i<5; i++) {
            for(int j=0; j<6; j++) {
                cout<<ans[i][j];
                if(j!=5)cout<<" ";
            }
            cout<<endl;
        }
    }
    return 0;
}

郭炜老师的代码：

#include <cstring>
#include <iostream>
using namespace std;
int GetBit(int c,int i) {//取c的第i位
    return  ( c >> i ) & 1;
}
void SetBit(int & c,int i, int v) {//设置c的第i位为v
    if( v )  c |= ( 1 << i);//如果v==1 或 
    else c &= ~( 1 << i);//置零 
}
void Flip(int & c, int i) {//将c的第i位为取反
    c ^= ( 1 << i);
    //1^0=1 0^0=0 A^0=A
    //A^1=!A
    //c ^= ( 1 << i); 这种写法可以对一个数操作 可以理解为一个二进制字串 
}
void OutputResult(int t,int result[]) {    //输出结果
    cout << "PUZZLE #" << 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 << " ";
        }
        cout << endl;
    }
}
int main()   {
    int oriLights[5];//最初灯矩阵，一个比特表示一盏灯
    int lights[5];    //不停变化的灯矩阵
    int result[5];    //结果开关矩阵
    int switchs;//某一行的开关状态
    int T;
    cin >> T;
    for( int t = 1; t <= T; ++ t) {
        memset(oriLights,0,sizeof(oriLights));
        for( int i = 0; i < 5; i ++ ) {    //读入最初灯状态
            for(  int j = 0; j < 6; j ++ ) {
                int s;
                cin >> s;
                SetBit(oriLights[i],j,s);
            }
        }
        for( int n = 0; n < 64; ++n ) {    //遍历首行开关的64种状态
            memcpy(lights,oriLights,sizeof(oriLights));
            switchs = n;//第i行的开关状态
            for( int i = 0; i < 5; ++i ) {
                result[i] = switchs;//第i行的开关方案
                for( int j = 0; j < 6; ++j ) {
                    if( GetBit(switchs,j)) {
                        if( j > 0) Flip(lights[i],j-1); //改左灯
                        Flip(lights[i],j);//改开关位置的灯
                        if( j < 5 ) Flip(lights[i],j+1);//改右灯
                    }
                }
                if( i < 4 ) lights[i+1] ^= switchs;//改下一行的灯
                switchs = lights[i]; //第i+1行开关方案和第i行灯情况同
            }
            if( lights[4] == 0 ) {
                OutputResult(t,result);
                break;
            }
        }
    }
    return 0;
}

再次吐槽牛客网不适合写博客我明明排好版了，因为tab所占字符数设置不一样又乱了，还不如笔记软件……

POJ 1222 优化穷举 位运算

POJ 1222 优化穷举位运算