题目详情

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

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

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

输入
两行，给出两个由0、1组成的等长字符串，表示当前/目标密码锁状态，其中0代表凹，1代表凸。
输出
至少需要进行的按按钮操作次数，如果无法实现转变，则输出impossible。
样例输入
011
000
样例输出
1

AC代码（内有详细思路，请放心食用^^）

#include<cmath>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char a[100086],b[100086];
int a1[100086],b1[100086],a2[1000086];
int main(){
    cin>>(a+1)>>(b+1);//本人比较喜欢从1开始，所以这里加1输入
    int len=strlen(a+1);//记录长度
    for(int i=1;i<=len;i++){
        a1[i]=a[i]-'0';
        a2[i]=a1[i];
        b1[i]=b[i]-'0';
    }
    int s1=0,s2=0;
    //1;
    s1++;
    int f1=0,f2=0;
        a1[1]=!a1[1];//1变成0，0变成1
        a1[2]=!a1[2];//这里分为两种情况，一种是第一个强改，第二个可以理解为顺其自然，找到两个里面较小的一个。这里首先将a1中的值强改，所以第一位第二位都要变成他对应的值
        for(int i=2;i<=len;i++){
            if(a1[i-1]!=b1[i-1]){//如果不匹配直接改
                s1++;
                a1[i-1]=!a1[i-1];
                a1[i]=!a1[i];//题目要求，改一个会影响周围
                a1[i+1]=!a1[i+1];
            }
            if(i==len&&a1[i]==b1[i]){//长度相等并且最后一位必须一样，这里不去管其他的数字的原因是因为这一位变化了，下一位如果不同还会变回来，或者说看到样例，011--000，这里再这个循环肯定不对，因为第一位不需要改，在下一个循环中会有详细i介绍
                f1=1;
            }
        }
        for(int i=2;i<=len;i++){
            if(a2[i-1]!=b1[i-1]){
                s2++;//这里和上面处理方法一样
                a2[i-1]=!a2[i-1];
                a2[i]=!a2[i];
                a2[i+1]=!a2[i+1];
            }
            if(i==len&&a2[i]==b1[i]){
                f2=1;//解释一下011--000，这里在第一个1的时候会改变前后的值，于是变成了100，可是这个和000不一样啊？问题不大，正确处理方法因该是最后一个1按下去，变换了000，可是这两个都是一步，有什么区别呢？有些人可能说是凑巧，不过可以多处几组数据试试奥
            }
        }
        if(f1==0&&f2==0){
            cout<<"impossible";//在上面处理的时候如果两个都不成那么就是不可能
            return 0;
        }
        if(f1==1&&f2==0){//这里找有答案的一个
            cout<<s1;
            return 0;
        }else if(f1==0&&f2==1){
            cout<<s2;
            return 0;
        }
        if(s1>s2){//都有答案找一个小的
            cout<<s2;
        }else{
            cout<<s1;
        }

    
}

@^ _ ^@