題目：特殊密碼鎖
001:特殊密碼鎖
描述
有一種特殊的二進制密碼鎖，由n個相連的按鈕組成（n<30），按鈕有凹/凸兩種狀態，用手按按鈕會改變其狀態。
然而讓人頭疼的是，當你按一個按鈕時，跟它相鄰的兩個按鈕狀態也會反轉。當然，如果你按的是最左或者最右邊的按鈕，該按鈕只會影響到跟它相鄰的一個按鈕。
當前密碼鎖狀態已知，需要解決的問題是，你至少需要按多少次按鈕，才能將密碼鎖轉變為所期望的目標狀態。
輸入
兩行，給出兩個由0、1組成的等長字符串，表示當前/目標密碼鎖狀態，其中0代表凹，1代表凸。
輸出
至少需要進行的按按鈕操作次數，如果無法實現轉變，則輸出impossible。
樣例輸入
011
000樣例輸出
1解題思路：首先我們能想到的是在確保x[i]之前的數據與y[i]相同的情況下，我們可以通過改變x[i+1]來使x[i]與y[i]保持相同，最后通過比較最后一位是否相同或者比較x與y是否相同來判斷兩者最終的結果。這里需要注意的是x[0]的狀態，x[0]的狀態有兩種方法來改變，一是通過改變x[1]來使x[0]改變，二是通過改變x[0]自身來改變，這里我們要分開討論，取兩種情況下的最小值作為最后的結果。
代碼：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <math.h>
#include<algorithm>
using namespace std;
char a[32],b[32],c[32];
int count1=0,count2=0,a1=1e10,a2=1e10;
int len;
void switchs(int i)
{a[i-1]=a[i-1]=='1'?'0':'1';a[i]=a[i]=='1'?'0':'1';if(i<len-1)a[i+1]=a[i+1]=='1'?'0':'1';
}
int compare(int n)
{int an=0;for(int i=1;i<n;i++){if(a[i-1]!=b[i-1]){switchs(i);an++;}}return an;
}
int main()
{while(cin>>c>>b){len = strlen(c);int sign = 0;strcpy(a,c);count1=compare(len);if(!strcmp(a,b)){a1=count1;sign=1;}strcpy(a,c);a[0]=a[0]=='1'?'0':'1';a[1]=a[1]=='1'?'0':'1';count2=compare(len)+1;if(!strcmp(a,b)){a2=count2;sign=1;}if(sign)cout<<min(a1,a2)<<endl;else cout<<"impossible"<<endl;}return 0;
}
