題目來源限制描述輸入輸出樣例輸入樣例輸出解題報告思路分析源代碼

題目

來源

中國MOOC網(wǎng)，程序設(shè)計(jì)與算法（二）第一周作業(yè)1 http://cxsjsxmooc.openjudge.cn/2017t2sPRinghw1/1/

限制

總時間限制: 1000ms 內(nèi)存限制: 1024kB

描述

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

然而讓人頭疼的是，當(dāng)你按一個按鈕時，跟它相鄰的兩個按鈕狀態(tài)也會反轉(zhuǎn)。當(dāng)然，如果你按的是最左或者最右邊的按鈕，該按鈕只會影響到跟它相鄰的一個按鈕。

當(dāng)前密碼鎖狀態(tài)已知，需要解決的問題是，你至少需要按多少次按鈕，才能將密碼鎖轉(zhuǎn)變?yōu)樗谕哪繕?biāo)狀態(tài)。

輸入

兩行，給出兩個由0、1組成的等長字符串，表示當(dāng)前/目標(biāo)密碼鎖狀態(tài)，其中0代表凹，1代表凸。

輸出

至少需要進(jìn)行的按按鈕操作次數(shù)，如果無法實(shí)現(xiàn)轉(zhuǎn)變，則輸出impossible。

樣例輸入

011 000

樣例輸出

1

解題報告

思路分析

首先思考枚舉法，每個按鈕有2種狀態(tài)，但是最多可能有30個燈，因此狀態(tài)有2^30之多，窮舉一定會超時。

重點(diǎn)1 一個燈如果按了第二下，就會抵消上一次按下所產(chǎn)生的影響。因此，一個燈只有按或者不按兩種情況，不存在一個燈要開關(guān)多次的情況。

例如八個燈 00000000 按1后 11000000 按3后 10110000 按1后 01110000 這和八個燈 00000000 只按一次3后 01110000 是完全相同的情況

重點(diǎn)2 我們只需要考慮是否按下第一個燈。因?yàn)槿绻谝粋€燈的狀態(tài)被確定了，那么是否按下第二個燈也就決定了（如果第一個燈與期望不同，則按下，如果期望相同，則不按下）同理，第三個燈是否按下也唯一確定。

所以，本題只要分兩種情況：燈1被按下和沒有被按下 之后使用for循環(huán)判斷別的燈是否需要按下即可 當(dāng)循環(huán)結(jié)束，若現(xiàn)在的燈況與答案相同，則輸出兩種方案中按鍵次數(shù)最少的，若不同，則impossible！

源代碼

很亂，我寫了一個Push函數(shù)專門負(fù)責(zé)改變燈的狀態(tài)，這里主要是要注意邊界條件（pos為0和len-1） 同時，為了方便轉(zhuǎn)換，我在進(jìn)入函數(shù)之前，將char類型的元素-48變?yōu)榱薸nt型，這樣1-0=1，1-1=0方便轉(zhuǎn)換，在函數(shù)結(jié)束時，將元素+48重新轉(zhuǎn)換為char類型方便使用strcmp函數(shù)進(jìn)行判斷