特殊密碼鎖

總時間限制:?

1000ms

內存限制:?

1024kB

描述

有一種特殊的二進制密碼鎖，由n個相連的按鈕組成（n<30），按鈕有凹/凸兩種狀態，用手按按鈕會改變其狀態。

然而讓人頭疼的是，當你按一個按鈕時，跟它相鄰的兩個按鈕狀態也會反轉。當然，如果你按的是最左或者最右邊的按鈕，該按鈕只會影響到跟它相鄰的一個按鈕。

當前密碼鎖狀態已知，需要解決的問題是，你至少需要按多少次按鈕，才能將密碼鎖轉變為所期望的目標狀態。

輸入

兩行，給出兩個由0、1組成的等長字符串，表示當前/目標密碼鎖狀態，其中0代表凹，1代表凸。

輸出

至少需要進行的按按鈕操作次數，如果無法實現轉變，則輸出impossible。

樣例輸入

011
000

樣例輸出?

1

分析

只需要考慮是否按下第一個燈。因為如果第一個燈的狀態被確定了，那么是否按下第二個燈也就決定了（如果第一個燈與期望不同，則按下，如果期望相同，則不按下）同理，第三個燈是否按下也唯一確定。

所以，本題只要分兩種情況：燈1被按下和沒有被按下?
之后使用for循環判斷別的燈是否需要按下即可?
當循環結束，若現在的燈況與答案相同，則輸出兩種方案中按鍵次數最少的，若不同，則impossible

代碼

#include <cstdio>
#include <cstring>
char str[33];
char str1[33];
char str2[33];
int len;
char change(char s){if(s == '1')return '0';else return '1';
}
int resolve(int p){for(int i = 2;i <= len;i++){/*驗證一下 str1的改變for(int j = 1;j <= len;j++)printf("%c",str1[j]);printf("\n");for(int j = 1;j <= len;j++)printf("%c",str2[j]);printf("\n");*/if(str1[i-1] != str2[i-1]){p++;str1[i] = change(str1[i]);if(i != len)str1[i+1] = change(str1[i+1]);}}//printf("%c vs %c\n",str1[len],str2[len]);if(str1[len] != str2[len])return -1;    //最后一個字符不相等，說明無法轉換為目標狀態return p;
}
int main(){scanf("%s",str+1);scanf("%s",str2+1);len = strlen(str+1);for(int i = 1;i <= len;i++)str1[i] = str[i];//將第一個按鈕按下str1[1] = change(str1[1]);str1[2] = change(str1[2]);int ans = resolve(1);//printf("ans:%d\n ",ans);//不按下第一個按鈕for(int i = 1;i <= len;i++) //這里要用str重置str1，因為它已經被改變了str1[i] = str[i];int ans2 = resolve(0);//printf("ans2:%d\n ",ans2);if(ans == ans2 && ans == -1)printf("impossible");else{if(ans == -1 || ans2 == -1)printf("%d",ans > ans2 ? ans : ans2);elseprintf("%d",ans < ans2 ? ans : ans2);}
}