001：特殊密码锁

问题还原

001:特殊密码锁

总时间限制: 1000ms 内存限制: 1024kB

描述

有一种特殊的二进制密码锁，由n个相连的按钮组成（n<30），按钮有凹/凸两种状态，用手按按钮会改变其状态。

然而让人头疼的是，当你按一个按钮时，跟它相邻的两个按钮状态也会反转。当然，如果你按的是最左或者最右边的按钮，该按钮只会影响到跟它相邻的一个按钮。

当前密码锁状态已知，需要解决的问题是，你至少需要按多少次按钮，才能将密码锁转变为所期望的目标状态。

输入

两行，给出两个由0、1组成的等长字符串，表示当前/目标密码锁状态，其中0代表凹，1代表凸。

输出

至少需要进行的按按钮操作次数，如果无法实现转变，则输出impossible。

样例输入1

011
000

样例输出1

1

样例输入2

01
11

样例输出2

impossible

解题分析

考虑使用枚举法解题，但是如果使用暴力穷举，将会产生2ⁿ次循环，在n接近30的时候，必然无法满足时间限制。

事实上，在使用枚举法的时候往往可以考虑一些最小结构。

例如，在熄灯问题中，给定一个固定大小的 0 1 矩阵，0代表熄灯，1代表亮灯，每个灯的开关都可以操作，每个开关都会使其本身及上下左右共五个块的数据产生翻转，若在边界处，其影响范围将对应减少。题目要求输出能将给定的矩阵变成全零矩阵的开关操作矩阵，简单的说就是把对应开关的操作写成矩阵，按开关就是1，不按开关就是0。 这个问题如果进行穷举的话将会更快的达到时间上线。

仔细观察可以发现，如果第一行灯的操作确定了，那么在进行第二行操作的时候，为了保证第一行一定是正确的，那么第二行的操作也将是确定的，如此循环下去，到达最后一行，只需要检查最后一行能否达到全零的目标即可。因此熄灯问题中，第一行就是最小结构。

回到密码锁的问题，这其实是对熄灯问题的一个简化。假设我们按照从左到右的顺序进行操作，如果给定了第一个按钮的状态，那么为了保证第一个按钮保持和目标的一致，第二个按钮的操作也将是确定的，这样循环下去，通过第n-1个按钮的状态确定了最后一个按钮的操作之后，只需要对比最后一个按钮和目标的最后一个按钮的状态就可以了。因此只需要对第一个按钮的状态进行枚举，只需要进行两次枚举即可。这样就解决了时间复杂度的问题。

代码实现中的几个关键部分

1. 输入的两个量作为字符串变量进行存储：

string ini,aim;
getline(cin,ini);
getline(cin,aim);

在这种输入下，字符串的长度测量使用，其中不包含最后的'\0'

int len = ini.size();

2. 数据的存储可以使用数组，但是为了减少代码的空间复杂度，可以使用位运算的方法来提高效率。主要的操作如下：

   • 将变量c的第i位置为v，其中v只能是0或1：

void SetBit(int &c, int i,char v) 
{

if(v == '1'){
c |= (1 << i);
}
else if (v == '0')
{
c &= ~(1 << i);
}
}

• 取变量c的第i位：

   int GetBit(int c,int i)//取c的第i位
   {
   return(c >> i) & 1;
   } 

• 翻转c的第i位

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

3. 不要忘记当不能正常输出时要输出异常报告：impossible.

源代码

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

int iniState;//存放原始状态
int aimState;//存放目标状态
int mixCount =999; //存放最小计数 

int GetBit(int c,int i)//取c的第i位
{
    return(c >> i) & 1;
 } 
 
 //设置c的第i位为v 
void SetBit(int &c, int i,char v) 
{
    
    if(v == '1'){
        c |= (1 << i);
    }
    else if (v == '0')
    {
        c &= ~(1 << i);
    }
}

//翻转c的第i位
void FlipBit(int &c, int i){
    c ^= (1 << i);
} 

int main()
{
    string ini,aim;
    getline(cin,ini);
    getline(cin,aim);
    
    int len = ini.size(); //len为输入的数据的长度
    int count=0,mixCount=999; //计算次数、最小计算次数      
    for (int i = 0;i<len;i++) //改为位表示 
    {
        SetBit(iniState,i,ini[i]);
        SetBit(aimState,i,aim[i]);
    }
    
    for(int n = 0; n < 2; n++) //枚举开头的两种可能
    {
        int state = iniState;
        int count = 0;

        int flag = n;//初始化标志位，1变0不变
        if(n){
            FlipBit(state,0); //处理第一个数据 
            FlipBit(state,1);//第二个数据也要翻转 
            count ++ ;
        }
        for(int i = 1; i < len; i++)  
        {
            if(GetBit(state,i-1) == GetBit(aimState,i-1))//若上个数据和目标一致，则flag为0
                flag = 0;
            else flag = 1;
            if(flag == 1) //需翻转
            {
                count ++ ;
                FlipBit(state,i); //翻转当前位
                 if(i != len-1)
                    FlipBit(state,i+1); //未到边界，翻转下一位。
                     //上一位不需要操作，只需对比最后一位即可 
             } 
         }
         //如果末位不一样，说明不可行，count置零 
         if(GetBit(state,len-1) != GetBit(aimState,len-1)) 
            count = 0;  
         if (count != 0)
         {
            if(count < mixCount)
                mixCount = count;
         }
        
     } 
    
     if(mixCount != 999)
        cout << mixCount <<endl;
    else 
        cout << "impossible"<<endl;
     return 0;
}