Mato is No.1

RQNOJ187 巧置擋板
———————————————————————————————————————————————————
【背景（神犇不要囧視，3x）】
本沙茶最近開始猛攻搜索、近似、隨機等算法，目標是A掉AHOI2012的后3題（在哪跌倒就從哪爬起）。昨天晚上找到這題，發現是搜索，于是開始捉……結果被折騰了一晚上加一上午才A掉，不過，看在這題可以系統性的反映DFS優化的一般步驟，忍了……另外，這題是本沙茶在RQNOJ上通過的第400題……回想起通過第300題的時候已經是近三年半之前了……真頹廢啊……
———————————————————————————————————————————————————
普通DFS（不加迭代）的優化方法主要有：
（1）可行性剪枝，如果遇到已經無法產生可行解的情況就剪枝，有時候，可行性剪枝也可以指在搜索過程中對不合法情況的剔除；
（2）最優性剪枝：如果遇到已經無法產生比目前得到的最優解還要優的解的情況就剪枝，這其中包括啟發式最優性剪枝（即分支限界），對目前解的進展情況作樂觀估計，如果估計值都不能超越目前的最優解，則剪枝；
（3）通過改變搜索順序，盡早得出較優解，從而為后面的剪枝提供余地；
（4）通過預處理等手段，提前得到啟發值或者較優解，為后面的剪枝提供余地；

一般步驟：
（1）預處理，當然是寫在最前面，在搜索前得到啟發值等東東；
（2）搜索過程中，先寫最優性剪枝（包括已經到達搜索終點了，也應該判斷一下，提前排除不是最優解的情況）；
（3）再判定搜索終點，如果到了，也不要馬上更新解，而是要判定這個解是否符合要求，再更新；
（4）若未到終點，再寫可行性剪枝；
（5）最后寫搜索過程，包括需要改變搜索順序的情況。

注意事項：數組的分層問題。
這是一個很嚴重的問題，因為分層出錯很可能會導致一些很怪的錯誤出現，難以發現。在搜索題的調試技巧這一篇中，已經提到了這個問題，本題又涉及到了。
一般來說，搜索過程中使用的數組（包括變量，可以視為零維數組）可以分為以下三類：
（1）在搜索過程中，只會引用其值，不會修改的數組（比如預處理中得到的那些東東），相當于常量；
（2）在搜索過程中，會改變其值，但在搜索完畢后能改回原值的數組；
（3）在搜索過程中，會改變其值，且在搜索完畢后也改不回原值的數組。
對于（1）（2）類數組，不需分層，但對于第（3）類數組一定要分層。這是因為這些數組在多層搜索中都需要修改，而且搜索完了也改不回來，如果不分層，則當后面的搜索完畢以后，要繼續搜索前面的，引用的將是后面的值，就會出錯。
對于第（3）類數組，有的已經“自然分層”（每層搜索修改的元素都不一樣），比如本題代碼中的R[][]、C[][]。然而有的并沒有自然分層，比如本題的len、pos[]、tmp[]等，因此對于這些數組，需要再加一維，對于不同層使用該維不同的元素即可。

下面是本題的算法：
使用DFS搜索每個位置的擋板是否需要放。搜索時，先搜豎的再搜橫的，由于題目要求每個連通塊都必須是矩形，因此對于豎的，如果該位置的上方兩個相鄰位置的橫的沒有全放（包括只放了一個），則該位置的豎的放不放取決于其上一行對應位置的豎的有沒有放（第一行除外），如果兩個橫的都放了，則這里的豎的既可以放也可以不放（先搜不放的情況）。當然，一行的兩個1之間必須至少有一個豎的，這是可行性限制。在搜橫的的時候，按照該行所放的豎的，分成若干段，顯然每一段要么下面都用橫的封上，要么一個都不封上。其中，如果該段所在的連通塊里面有1，且下一行對應位置也有1，則必須封上；若該段所在連通塊里面沒有1，則不能封上（因為不能有一個連通塊里一個1都沒有），否則可以自由選擇封還是不封（當然也是先搜不封的）。這樣一直搜到最后一行的豎的后，還要判斷最后一行有沒有連通塊里沒1，若沒有，則為一個可行解。啟發式優化：設D[i]為第i行及以后至少要幾個擋板（若某行有K個1，則至少需要(K-1)個豎的；若某列有K個1，則至少需要(K-1)個橫的，累加起來即可，顯然這是樂觀估計），D[i]可以預處理出來，當做啟發值。

代碼：