链接： http://cxsjsxmooc.openjudge.cn/2021t2springall/001/

image.png

image.png

#include <iostream>
using namespace std;

int GetBit(int c,int i){
    return (c >> i) & 1;
}

void SetBit(int & c,int i,int v){
    if(v){
        c |= (1 << i);
    }else{
        c &= ~(1 << i);
    }
}

void Shift(int & c,int i){
    c ^= (1 << i);
}


int main(){
    // 读入数据并且存储
    char origin[30];
    cin >> origin;
    char target[30];
    cin >> target;
    
    //存为二进制形式，因为不超过30位，存给整型变量
    int start=0;    //初始状态
    int num=0;      //记录输入灯的长度
    for(int i = 0; origin[i] != '\0';i++){
        num ++;
        SetBit(start,i,origin[i]-'0');
    }

    int end=0;    //目标状态
    for(int i = 0; target[i] != '\0';i++){
        SetBit(end,i,target[i]-'0');
    }
    int change;    //变化灯矩阵
    
    //枚举
    /*
    当第一个开关的状态确定之后，灯有了新的状态，第二个开关的状态也会被确定下来
    why：若第一个开关使得第一个灯的状态与目标状态一致，那么第二个开关应该不操作，
    如果不一致需要按下第二个开关来抵消第一个开关的影响
    */
    
    int flag = 0;   //作为标识，标识有没有解
    //枚举第一个灯的两种状态
    for(int n = 0;n<2;n++){
        //一定要在这重循环里给change初始化————reason：保证每次枚举的都是origin灯的状态
        change = start;
     
        int r = 0;    //记录要按几次开关
        int switches;
        switches = n;
        for(int j = 0;j<num;j++){
            //这重循环里，每一次开关的状态都是提前确定的
            if(switches){
                r++;
                Shift(change,j);
                if(j > 0){
                    Shift(change,j-1);
                }
                if(j < num-1){
                    Shift(change,j+1);
                }
            }if(change == end){
                cout << r << endl;
                flag = 1;
                break;
            }if(GetBit(end,j) == GetBit(change,j)){
                switches = 0;
            }if(GetBit(end,j) != GetBit(change,j)){
                switches = 1;
            }
        }
        if(flag){
            break;
        }
    }
    if(!flag){
        cout << "impossible" << endl;
    }
}

遇到的问题：

• 枚举 * 也就是枚举 个开关所有的状态，导致程序的效率低下，不能在规定时间内完成

• 后来我有仔细想了郭老师的例子：发现它是利用枚举第一行开关的状态，利用下一行开关完全取决于上一行开关操作结束后灯的状态决定。

• 虽然写的是循环，实际上也可以是递归，第一行开关确定之后，第二行相当于2-n行灯的第一行矩阵

• 故，可以尝试用递归程序写