本文共 1940 字，大约阅读时间需要 6 分钟。

描述

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

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

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

输入

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

输出

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

思路：   一个按钮按两下相当于没按， 按三下相当于按一下。

             按下一个按钮保证前面的灯都是符合期望状态，枚举到最后一盏灯如果也可以符合期望状态，即可以实现转变。

             eg: 如果第 i 盏 不符合期望状态， 按下第 i+1 盏灯 ， 第 i 盏灯则会符合期望状态 ， 不影响前面的状态。 

             特殊情况： 第一盏灯，前面没灯限制， 所以要考虑两种情况， 按第一盏灯， 不按第一盏灯。

                              数据：110   000 ； 101  000；

                              最后两盏灯， 只能按下最后一盏灯改变两盏灯， 或者都不按。 

                              数据：011  000；

代码：

#include <stdio.h>#include <string.h>const int N = 35;char a[N], b[N], c[N];char fan(char ch) // 按下的翻转操作{    if(ch == '1')        return ch = '0';    return ch = '1';}int main(){    scanf ("%s %s",a,b);    strcpy(c, a);    int alen, blen;    alen = strlen(a);    blen = strlen(b);    int ans = 0;    for(int i=0; i <= alen - 2; i++) // 不按第一盏灯的情况    {        if(a[i] != b[i]) // 如果第 i盏灯 不符合期望状态        {            ans ++;            if(i < alen-2) // 如果不是最后两盏灯按下 第 i+1 盏灯            {                a[i] = fan(a[i]);                a[i+1] = fan(a[i+1]);                a[i+2] = fan(a[i+2]);            }            else  // 最后两盏只能按下最后一盏灯            {                a[i] = fan(a[i]);                a[i+1]	= fan(a[i+1]);            }        }    }    int ans1 = 1; // 按第一盏灯的情况    c[0] = fan(c[0]), c[1] = fan(c[1]);    for(int i=0; i <=alen-2; i++)    {        if(c[i] != b[i]) // 如果第 i盏灯 不符合期望状态        {            ans1 ++;            if(i < alen-2) // 如果不是最后两盏灯按下 第 i+1 盏灯            {                c[i] = fan(c[i]);                c[i+1] = fan(c[i+1]);                c[i+2] = fan(c[i+2]);            }            else  // 最后两盏只能按下最后一盏灯            {                c[i] = fan(c[i]);                c[i+1] = fan(c[i+1]);            }        }    }    if(strcmp(a, b) == 0)        printf("%d\n",ans);    else if(strcmp(b, c) == 0)        printf("%d\n",ans1);    else        printf("impossible\n");    return 0;}