二进制密码锁
描述：
在海拉鲁大陆有一种特殊的二进制密码锁，由n个相连的按钮组成（n<30），按钮有凹/凸两种状态，用手按按钮会改变其状态。
然而让人头疼的是，当按一个按钮时，跟它相邻的两个按钮状态也会反转。当然，如果按的是最左或者最右边的按钮，该按钮只会影响到跟它相邻的一个按钮。
当前密码锁状态已知，需要解决的问题是，林克至少需要按多少次按钮，才能将密码锁转变为所期望的目标状态。
输入
两行，给出两个由0、1组成的等长字符串，表示当前/目标密码锁状态，其中0代表凹，1代表凸。
输出
至少需要进行的按按钮操作次数，如果无法实现转变，则输出impossible。
输入样例 1
011 000
输出样例 1
1
题解：
当某一个按钮状态确定后，它的下一个按钮按与不按取决于这一个与目标状态是否一致，所以后续所有按钮其实都只取决于第一个按钮。
枚举共两种情况：第一个按钮按（用1标记），第一个按钮不按（用0标记）
最多次数为30次，故最终结果res初始化为31，用于判断impossible的情况
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 int main() 5 { 6 string init, result; // 要操作的，预期的 7 string temp; // 记录当前状态 8 cin >> init >> result; 9 int n = init.length(), res = 31; // 最多加30次 10 for (int i = 0; i < 2; ++i) 11 { 12 // 当前状态 13 temp = init; 14 15 int next = i, times = 0; 16 17 for (int j = 0; j < n; ++j) 18 { 19 if (next == 1) 20 { 21 /////////////////// 22 if (j > 0) 23 temp[j - 1] ^= 1; //^1即实现取反的效果 24 temp[j] ^= 1; 25 if (j < n - 1) 26 temp[j + 1] ^= 1; 27 /////////////////// 28 // 以上实现相邻3位取反（边缘为2位） 29 30 times++; // 操作次数加1 31 } 32 if (temp[j] == result[j]) // 若两位相同，则不用按下一位 33 next = 0; 34 else // 若不同，则要按下一位 35 next = 1; 36 if (temp == result) // 如果能达到预期结果 37 { 38 res = min(res, times); // 记录最小操作数 39 break; 40 } 41 } 42 } 43 if (res != 31) 44 cout << res; 45 else // 无法达到预期 46 cout << "impossible"; 47 48 return 0; 49 }