- 总时间限制: 1000ms内存限制: 1024kB
- 描述
-
有一种特殊的二进制密码锁，由n个相连的按钮组成（n<30），按钮有凹/凸两种状态，用手按按钮会改变其状态。
然而让人头疼的是，当你按一个按钮时，跟它相邻的两个按钮状态也会反转。当然，如果你按的是最左或者最右边的按钮，该按钮只会影响到跟它相邻的一个按钮。
当前密码锁状态已知，需要解决的问题是，你至少需要按多少次按钮，才能将密码锁转变为所期望的目标状态。
- 输入
- 两行，给出两个由0、1组成的等长字符串，表示当前/目标密码锁状态，其中0代表凹，1代表凸。
- 输出
- 至少需要进行的按按钮操作次数，如果无法实现转变，则输出impossible。
样例输入1
011
000
样例输出1
1
样例输入2
111
101
样例输出2
3
样例2说明：111--->001(按下第一个)--->110(按下第二个)--->101(按下第三个)
算法分析：枚举+贪心
参考 熄灯问题的讲解http://www.cnblogs.com/huashanqingzhu/p/7278930.html
本题算是熄灯问题的简化版。 枚举第一个按钮是否按下的两种情况即可。第一个按钮的操作情况确定以后，后面的事情都是确定的。
也即，当第一个按钮操作完成以后，从第二个开始扫描：若发现前一个没有达到目的状态，只能通过操作当前按钮去修改前一个按钮的状态。以此类推，扫描完所有按钮为止。
最后：检验最后面一个按钮是否达到目的状态，若达到则该方案可以完成任务，但不一定是最优解（次数不一定是最小的。）因为第一个按钮的操作方案有两种。
所以要对第一个按钮的两种方案都做枚举求出各个方案对应的解，才能求最优解。
代码：
1 #include<stdio.h> 2 #include<string.h> 3 int main(int argc, char *argv[]) 4 { 5 char src[35],target[35],temp[35]; 6 int i,len; 7 int count,ans=1e9; 8 9 scanf("%s%s",src,target); 10 len=strlen(src); 11 strcpy(temp,src); 12 13 //第一种方案：第一个字符不修改，从下一个字符开始。 14 i=0;count=0; 15 i++; 16 while(src[i]!='\0') 17 { 18 if(src[i-1]!=target[i-1])//前一个元素不等，需要操作当前元素。操作当前元素影响到其左右元素。 19 { 20 src[i]=src[i]^1;//取反 21 src[i-1]=src[i-1]^1; 22 if(i+1<len) src[i+1]=src[i+1]^1; 23 count++; 24 } 25 i++; 26 } 27 if(src[len-1]==target[len-1]) ans=count; 28 29 //第二种方案：第一个字符修改 30 strcpy(src,temp); 31 i=0;//i重新指向第一个字符 32 src[i]=src[i]^1; 33 if(i+1<len) src[i+1]=src[i+1]^1; 34 count=1; 35 i++; 36 while(src[i]!='\0') 37 { 38 if(src[i-1]!=target[i-1])//前一个元素不等，需要操作当前元素。操作当前元素影响到其左右元素。 39 { 40 src[i]=src[i]^1;//取反 41 src[i-1]=src[i-1]^1; 42 if(i+1<len) src[i+1]=src[i+1]^1; 43 count++; 44 } 45 i++; 46 } 47 if(src[len-1]==target[len-1]) ans=ans<count?ans:count; 48 49 if(ans==1e9) printf("impossible\n"); 50 else printf("%d\n",ans); 51 return 0; 52 }
可以参考：http://www.cnblogs.com/candy99/p/5791488.html
