二进制枚举

北京大学mooc程序设计与算法二

image.png

分析：
枚举什么：
- 枚举所有开关的状态，那就有 $2^n$ 复杂度太高
- 通过观察发现当第一行状态确定的时候下面的开关的按法也是确定的：
  - 当第一行第j个灯是亮时，第2行第j个开关就要改变状态；以此类推，第二行的整体状态也会被确定下来，递归第三行，第四行，第五行都会确定下来
  - 最后通过观察最后一行灯是否全灭，既可知道该问题有没有解
  - $\rightarrow$ 我们只需要枚举第一行灯的状态
怎么存储输入的data
- 用整数数组存储，会造成大量的内存浪费，因为灯只有两种状态，我们考虑用二进制存储
- 要用到位运算的知识
- 我们用char型二进制来存数据

代码：

# include<iostream>
# include<memory>
# include<cstring>
using namespace std;

//取出第i位
/*
将第i位移到低位，和1做&运算
*/
int GetBit(char c,int i){
    return (c >> i) & 1 
}

//设置字符的第i位
/*
char 类型有2个字节16位，其中低6位是我们要的data
设置字符c的第i位的值为v
*/
void SetBit(char c,int i,int v){
    if(v){
        //c与 1的二进制左移i位（除了第i位为1，其余位为0）做或运算
        //保证了其他位不变而i位置1
        c |= (1 << i);
    }else{
        c &= ~(1 << i);
    }
}

//模拟开关反转
//采用引用传递的原因：这里我们希望真正改变实参，并且在主函数里会把这个变化存在变化数组里
//异或门可以用与或非门实现，，这里也体会了异或门的重要作用
void Flip(char &c, int i){
    c ^= (1 << i);
}

//输出结果
void outputResult(int t,char 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 << ends;
            }
        }
        cout << endl;
    }
}

int main(){
    char oriLights[5]; //最初的灯矩阵
    char Lights[5]; //变化的灯矩阵
    char result[5]; //要输出的开关矩阵
    char switches; //存储某一行开关的状态
    
    int T;
    cin >> T;
    for(int i = 0;i < T;i++){
        //对oriLights 初始化
        memset(oriLights,0,sizeof(oriLights));
        for(int j = 0;j<5;j++){
            for(int t = 0;t<6;t++){
                int s;
                cin >> s;
                SetBit(oriLights[i],t,s);
            }
        }
        //对第一行灯的状态进行穷举
        //每一个n代表一个整数，他的二进制表示即为第一行灯的一个状态，第一行开关有六位，
        // n循环一次，循环里要模拟第0行设置为n的二进制表示时对应的灯矩阵和开关矩阵
        for(int n = 0;n < 64;n++){
            //先把oriLights 复制给Lights下面的操作都是对Lights进行的
            switches = n;
            
            //处理第i行灯
            for(int i = 0;i < 5;i++){
                //把i行开关状态存起来
                result[i] = switches;
                //j表示第i行第j个灯
                //下面表示根据开关的情况来关开关所在行的灯
                for(int j = 0;j<6;j++){
                    if (GetBit(switches)){
                        Flip(Lights[i],j);
                        if(j>0){
                            Flip(Lights[i],j-1);
                        }
                        if(j<5){
                            Flip(Lights[i],j+1);
                        }
                    }
                }
                
                if(i<4){
                    //改变下一行灯的情况
                    Lights[i+1] ^= switches;
                }
                switches = Lights[i]; //确定第i行开关的状态
            }
            if(Lights[4] == 0){
                OutputResult(t,result);
                break;
            }
        }
    }
    return 0;
}

二进制枚举

二进制枚举

推荐阅读更多精彩内容