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

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

注意事項(xiàng)：數(shù)組的分層問(wèn)題。
這是一個(gè)很嚴(yán)重的問(wèn)題，因?yàn)榉謱映鲥e(cuò)很可能會(huì)導(dǎo)致一些很怪的錯(cuò)誤出現(xiàn)，難以發(fā)現(xiàn)。在搜索題的調(diào)試技巧這一篇中，已經(jīng)提到了這個(gè)問(wèn)題，本題又涉及到了。
一般來(lái)說(shuō)，搜索過(guò)程中使用的數(shù)組（包括變量，可以視為零維數(shù)組）可以分為以下三類：
（1）在搜索過(guò)程中，只會(huì)引用其值，不會(huì)修改的數(shù)組（比如預(yù)處理中得到的那些東東），相當(dāng)于常量；
（2）在搜索過(guò)程中，會(huì)改變其值，但在搜索完畢后能改回原值的數(shù)組；
（3）在搜索過(guò)程中，會(huì)改變其值，且在搜索完畢后也改不回原值的數(shù)組。
對(duì)于（1）（2）類數(shù)組，不需分層，但對(duì)于第（3）類數(shù)組一定要分層。這是因?yàn)檫@些數(shù)組在多層搜索中都需要修改，而且搜索完了也改不回來(lái)，如果不分層，則當(dāng)后面的搜索完畢以后，要繼續(xù)搜索前面的，引用的將是后面的值，就會(huì)出錯(cuò)。
對(duì)于第（3）類數(shù)組，有的已經(jīng)“自然分層”（每層搜索修改的元素都不一樣），比如本題代碼中的R[][]、C[][]。然而有的并沒(méi)有自然分層，比如本題的len、pos[]、tmp[]等，因此對(duì)于這些數(shù)組，需要再加一維，對(duì)于不同層使用該維不同的元素即可。

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

代碼：