程序设计与算法二郭炜枚举001特殊密码锁及解题思路

本文主要是介绍程序设计与算法二郭炜枚举001特殊密码锁及解题思路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

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

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

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

输入

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

输出

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

样例输入

011
000

样例输出

解题方法

使用两个int型的变量保存初始值和最终值，通过位运算改变每个bit的状态。枚举第一个bit也就是第一个按钮的两种情况，按下第一个按钮，第一个bit反转后可能的按键次数，这是第一种情况；不按下第一个按钮，第一个bit不发生反转后续可能的按键次数，这是第二种情况。

代码实现

# include <iostream>
# include <cstring>
# include <string>
# include <memory>
using namespace std;int Getbit(int a, int i)
{return (a>>i)&1;
}int Setbit(int &a, int i, int b)
{if(b) a |= (1<<i);else a &= ~(1<<i);
}int Filtbit(int &a, int i)
{a ^= (1<<i);
}int OutputResult(int result)
{if(result>=0) cout<<result;else cout<<"impossible";
}int main()
{int init=0,mid=0,end=0,cnt=0,result1=0,result2=0;char line[30];//输入数据cin>>line;cnt = strlen(line);for(int i=0;i<cnt;i++) Setbit(init,i,line[i]-'0');cin>>line;for(int i=0;i<cnt;i++) Setbit(end,i,line[i]-'0');//不按下第一个按钮的情况mid = init;for(int i=0;i<cnt-1;i++){if(Getbit(mid,i)!=Getbit(end,i)){Filtbit(mid,i);Filtbit(mid,i+1);if(i<cnt-2&&i!=0) Filtbit(mid,i+2);result1++;}if(mid==end){OutputResult(result1);break;}}//按下第一个按钮的情况if(mid!=end){mid = init;//按下第一个按钮Filtbit(mid,0);Filtbit(mid,1);result2++; for(int i=0;i<cnt-1;i++){if(Getbit(mid,i)!=Getbit(end,i)){Filtbit(mid,i);Filtbit(mid,i+1);if(i<cnt-2) Filtbit(mid,i+2);result2++;}if(mid==end){OutputResult(result2);break;}}}if(cnt==1){result1 = 1;OutputResult(result1);}else if(mid!=end){result1 = -1;OutputResult(result1);}return 0;
}