Tube's World

Q: http://poj.org/problem?id=1753

使用recursive做窮舉即可算出答案(2^16種情況)

因為piece不是白就是黑,2種情況而已

所以可以用bitwise operation來做運算方面的加速

概念:

先假設翻轉0顆的情況即可滿足goal

沒有滿足的話就在再假設翻轉1顆的情況(此時就開始跑recursive,看看是要翻第一顆, 還是第二顆.....)

如果沒有的話就再假設翻轉2顆的情況(是1,2顆,還是1,3顆........)

只要有滿足goal的情況出現,即可印出答案

如果跑到16顆都還是沒有滿足的話就印出impossible

recursive的概念則大概可以用以下pseudo code表示

void go(座標)

{

    flip(當前piece的座標) //翻轉當前piece

    go(下一個piece的座標) //在當前piece已經被翻轉的情況下,進行下一個piece的翻轉動作

    flip(當前piece的座標) //將當前piece給翻回來,等於沒被翻過

    go(下一個piece的座標) //在當前piece沒被翻轉的情況下,進行下一個piece的翻轉動作

}

不過當初因為沒看清楚題意

WA了5次= =

蠢哉土伯