PKU3254-Corn Fields

題目：http://poj.org/problem?id=3254
現在FJ有個N*M格的原野想要放牧，有些格子可以放牛、有些格子不能放牛
(最大12*12)
並且，上下或左右相鄰的兩個格子不能同時放牧
請問總共有多少種不同的放牧方法呢？(全部不放也是一種方法)


程式碼：http://codepad.org/8bqPnHT1
相關題單與具體作法來源：http://accry-best.appspot.com/?p=60003

狀態壓縮DP！終於寫到這樣的題目了
數字看起來那麼小，但是又無法全局暴力破解？

(1是放、0是不放)
假如我們已經知道一橫行，有哪些合法的方法，例如範例測資第一橫行：
000,001,010,100,101
而下一橫行獨立來說有000,010這兩種方法

[ (1)各自考慮完障礙物->(2)考慮橫行內牽制->(3)考慮不同橫行間的牽制 ]

獨立一橫行的可行解全部算出以後，
我們可以利用位元運算輕易的知道哪些方案可以配哪些方案，它們分別是
第二橫行000：對上第一橫行全部(1*5=5)
第二橫行010：對上第一橫行000,001,100,101(1*4=4)
加起來是9

所以整個觀念就是，工作(1)和(2)用二進位暴力的方式完成
(想像整個牧場的資料都投影到y軸，變成一柱狀長條)
於是只剩下行互相牽制，工作(3)可以順利地用DP來解決

心得：
從這作法的複雜度來看，
其實這題可以出成M到12、N到100之類的
也就是"狹長形"

又暴力又轉經典作法，讓人想起了2004年樓教主的論文
《淺談部分搜索+高效算法在搜索問題中的應用》
在暴力的部分細心決定特殊的點，
最後能讓case變成一張張的二分圖、進而漂亮解決的作法