问题还原
001:特殊密码锁
总时间限制: 1000ms 内存限制: 1024kB
描述
有一种特殊的二进制密码锁，由n个相连的按钮组成（n<30），按钮有凹/凸两种状态，用手按按钮会改变其状态。
然而让人头疼的是，当你按一个按钮时，跟它相邻的两个按钮状态也会反转。当然，如果你按的是最左或者最右边的按钮，该按钮只会影响到跟它相邻的一个按钮。
当前密码锁状态已知，需要解决的问题是，你至少需要按多少次按钮，才能将密码锁转变为所期望的目标状态。
输入
两行，给出两个由0、1组成的等长字符串，表示当前/目标密码锁状态，其中0代表凹，1代表凸。
输出
至少需要进行的按按钮操作次数，如果无法实现转变，则输出impossible。
样例输入1
011
000
样例输出1
1
样例输入2
01
11
样例输出2
impossible
解题分析
考虑使用枚举法解题，但是如果使用暴力穷举，将会产生2n次循环，在n接近30的时候，必然无法满足时间限制。
事实上，在使用枚举法的时候往往可以考虑一些最小结构。
例如，在熄灯问题中，给定一个固定大小的 0 1 矩阵，0代表熄灯，1代表亮灯，每个灯的开关都可以操作，每个开关都会使其本身及上下左右共五个块的数据产生翻转，若在边界处，其影响范围将对应减少。题目要求输出能将给定的矩阵变成全零矩阵的开关操作矩阵，简单的说就是把对应开关的操作写成矩阵，按开关就是1，不按开关就是0。 这个问题如果进行穷举的话将会更快的达到时间上线。
仔细观察可以发现，如果第一行灯的操作确定了，那么在进行第二行操作的时候，为了保证第一行一定是正确的，那么第二行的操作也将是确定的，如此循环下去，到达最后一行，只需要检查最后一行能否达到全零的目标即可。因此熄灯问题中，第一行就是最小结构。
回到密码锁的问题，这其实是对熄灯问题的一个简化。假设我们按照从左到右的顺序进行操作，如果给定了第一个按钮的状态，那么为了保证第一个按钮保持和目标的一致，第二个按钮的操作也将是确定的，这样循环下去，通过第n-1个按钮的状态确定了最后一个按钮的操作之后，只需要对比最后一个按钮和目标的最后一个按钮的状态就可以了。因此只需要对第一个按钮的状态进行枚举，只需要进行两次枚举即可。这样就解决了时间复杂度的问题。
代码实现中的几个关键部分
- 输入的两个量作为字符串变量进行存储：
string ini,aim;
getline(cin,ini);
getline(cin,aim);
在这种输入下，字符串的长度测量使用，其中不包含最后的'\0'
int len = ini.size();
-
数据的存储可以使用数组，但是为了减少代码的空间复杂度，可以使用位运算的方法来提高效率。主要的操作如下：
- 将变量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);
}
- 不要忘记当不能正常输出时要输出异常报告：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;
}
