題目來源限制描述輸入輸出樣例輸入樣例輸出解題報告思路分析源代碼
中國MOOC網，程序設計與算法（二）第一周作業1 http://cxsjsxmooc.openjudge.cn/2017t2sPRinghw1/1/
總時間限制: 1000ms 內存限制: 1024kB
有一種特殊的二進制密碼鎖，由n個相連的按鈕組成（n<30），按鈕有凹/凸兩種狀態，用手按按鈕會改變其狀態。
然而讓人頭疼的是，當你按一個按鈕時，跟它相鄰的兩個按鈕狀態也會反轉。當然，如果你按的是最左或者最右邊的按鈕，該按鈕只會影響到跟它相鄰的一個按鈕。
當前密碼鎖狀態已知，需要解決的問題是，你至少需要按多少次按鈕，才能將密碼鎖轉變為所期望的目標狀態。
兩行，給出兩個由0、1組成的等長字符串，表示當前/目標密碼鎖狀態，其中0代表凹，1代表凸。
至少需要進行的按按鈕操作次數，如果無法實現轉變，則輸出impossible。
011 000
1
首先思考枚舉法，每個按鈕有2種狀態，但是最多可能有30個燈，因此狀態有2^30之多，窮舉一定會超時。
重點1 一個燈如果按了第二下，就會抵消上一次按下所產生的影響。因此，一個燈只有按或者不按兩種情況，不存在一個燈要開關多次的情況。
例如八個燈 00000000 按1后 11000000 按3后 10110000 按1后 01110000 這和八個燈 00000000 只按一次3后 01110000 是完全相同的情況
重點2 我們只需要考慮是否按下第一個燈。因為如果第一個燈的狀態被確定了，那么是否按下第二個燈也就決定了（如果第一個燈與期望不同，則按下，如果期望相同，則不按下）同理，第三個燈是否按下也唯一確定。
所以，本題只要分兩種情況：燈1被按下和沒有被按下 之后使用for循環判斷別的燈是否需要按下即可 當循環結束，若現在的燈況與答案相同，則輸出兩種方案中按鍵次數最少的，若不同，則impossible！
很亂，我寫了一個Push函數專門負責改變燈的狀態，這里主要是要注意邊界條件（pos為0和len-1） 同時，為了方便轉換，我在進入函數之前，將char類型的元素-48變為了int型，這樣1-0=1，1-1=0方便轉換，在函數結束時，將元素+48重新轉換為char類型方便使用strcmp函數進行判斷
#include <stdio.h>#include <string.h>char s[35] = {0};char s2[35] = {0};int len = 0;char e[35]={0};void Push( int pos, char led[] );int main(){ //這兩個f是干嘛的，我寫的時候應該知道，但是現在只有上帝知道 int f1 = 0; int f2 = 0; int i = 0; int r1 = 0; int r2 = 0; scanf("%s",s); len = strlen(s); for( i=0;i<len;i++) s2[i] = s[i]; s2[i] = '/0'; scanf("%s",e); r1 = 1; Push(0,s); for( i = 1 ; i < len ; i ++ ) { if( s[i-1] != e[i-1] ) { Push(i,s); r1++; } } if(strcmp(s,e)!=0) f1=1; r2 = 0; for( i = 1 ; i < len ; i ++ ) { if( s2[i-1] != e[i-1] ) { Push(i,s2); r2++; } } if(strcmp(s2,e)!=0) f2=1; if( f1 == 1 && f2 == 1 ) { printf("impossible"); return 0; } if( f1 == 1 && f2 == 0 ) { printf("%d",r2); return 0; } if( f1 == 0 && f2 == 1 ) { printf("%d",r1); return 0; } if( r1 < r2 ) printf("%d",r1); else printf("%d",r2); return 0;}void Push( int pos, char led[] ){ if(pos>0) led[ pos - 1 ]-=48; led[pos]-=48; if(pos<len-1) led[ pos + 1 ]-=48; if( pos == 0 ) { led[pos] = 1 - led[pos]; led[ pos + 1 ] = 1 - led[ pos + 1 ]; } else if( pos == len-1 ) { led[ len-1 ] = 1 - led[len-1]; led[ len - 2 ] = 1 - led[ len - 2 ]; } if( pos > 0 && pos < len-1 ) { led[pos] = 1 - led[pos]; led[ pos + 1 ] = 1 - led[ pos + 1 ]; led[ pos - 1 ] = 1 - led[ pos - 1 ]; } if(pos>0) led[ pos - 1 ]+=48; led[pos]+=48; if(pos<len-1) led[ pos + 1 ]+=48;}/* * ┏┓ ┏┓ *┏┛┻━━━┛┻┓ *┃ ┃ *┃ ━ ┃ *┃ ┳┛ ┗┳ ┃ *┃ ┃ *┃ ┻ ┃ *┃ ┃ *┗━┓ ┏━┛ * ┃ ┃神獸保佑 * ┃ ┃代碼無BUG！ * ┃ ┗━━━┓ * ┃ ┣┓ * ┃ ┏┛ * ┗┓┓┏━┳┓┏┛ * ┃┫┫ ┃┫┫ * ┗┻┛ ┗┻┛ * */新聞熱點
疑難解答
