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个按钮的状态确定了最后一个按钮的操作之后，只需要对比最后一个按钮和目标的最后一个按钮的状态就可以了。因此只需要对第一个按钮的状态进行枚举，只需要进行两次枚举即可。这样就解决了时间复杂度的问题。
#include <stdio.h> void oriPass(int *a,int position,char n); void FlipBit(int *c, int i); int GetBit(int n,int position); int a,b,c; int switches = 1; int main() { int i,j; int n; char s; int num; int result = 0; int minResult = 1000; for(j = 0; (s=getchar())!= '\n' ; ++j) { oriPass(&a,j,s); } for(i = 0; (s=getchar())!= '\n'; ++i) { oriPass(&b,i,s); } num = i; for(i = 0; i < 2; ++i) { switches = i; result = 0; c = a; for(j = 0; j < num; ++j){ if(GetBit(switches,0)){ result++; FlipBit(&c,j); if(j > 0) FlipBit(&c,j-1); if(j < num - 1) FlipBit(&c,j+1); } switches = !(GetBit(c,j)==GetBit(b,j)); } if(b == c && minResult > result){ minResult = result; } } if(minResult == 1000) printf("impossible"); else printf("%d",minResult); return 0; } void oriPass(int *a,int position,char n) { if(n - 48) *a |= (1 << position); else *a &= ~(1 << position); } void FlipBit(int *c, int i) { *c ^= (1 << i); //把c的第i为取反 } int GetBit(int n,int position) { return (n >> position) & 1; }ps:本体最难的地方在于能不能想到枚举的可能方法只有两种，并且在进行枚举时每轮的switches的值的变换很值得研究，我在这里卡了很久。
