PKU3279-Fliptile

題目：http://poj.org/problem?id=3279
(經典燈泡遊戲)
有一個至多15*15的黑白棋盤格
每次可以選擇某個位置進行「操作」，使該位置+四周黑變白白變黑
輸出操作數最少的方案使得棋盤全部變白，如果有多個方案應輸出字典序最小的

/*
事實上，本人驗過原USACO測資、全部只有一組解…字典序可以無視
*/



程式碼：codepad掛了，待補
顯而易見可能的操作數有2^(NM)那麼多種
但是要求操作完必須全白、而每個操作影響範圍又那麼小
讓人很容易聯想到：第一行的操作方案決定了一切

假設盤面前兩行是這樣的：

0 0 0 0 1 0 1 0
0 0 0 0 0 0 1 0

當我決定第一行的操作是(1表示操作、0表示不動)
1 1 1 0 1 1 0 0
那麼第一行和第二行的狀態會變成：

0 1 0 0 1 0 0 0
1 1 1 0 0 0 1 0

注意紅色字是被改變後的第一行
想讓1變回0只有一種可能：它的下一格必須有操作
想讓0保持不動也只有一種情形：它的下一格必須不操作

如此一來第二行的操作方案就非得是
0 1 0 0 1 0 0 0
不可了

有了這個最核心的發現，時間複雜度就降到了2^min(N,M)

其中不論是用位運算或是陣列操作都得謹慎才行，算是比較要注意coding細節