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è)很?chē)?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ā)值。
代碼：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
const int MAXN = 35, INF = ~0U >> 2;
int n, m, D[MAXN], len[MAXN], pos[MAXN][MAXN], tmp[MAXN][MAXN], res = INF;
bool A[MAXN][MAXN], C[MAXN][MAXN], R[MAXN][MAXN], S[MAXN][MAXN][MAXN][MAXN];
void dfs0(int No, int v, int sum, bool FF);
void init()
{
scanf("%d%d", &n, &m); int x;
re(i, n) re(j, m) {scanf("%d", &x); A[i][j] = x;}
}
void prepare()
{
re(i, n) re(j, m) {
S[i][j][i][j] = A[i][j];
re2(k, i+1, n) S[i][j][k][j] = A[k][j] || S[i][j][k - 1][j];
re2(k, j+1, m) S[i][j][i][k] = A[i][k] || S[i][j][i][k - 1];
re2(k, i+1, n) re2(k0, j+1, m) S[i][j][k][k0] = A[k][k0] || S[i][j][k - 1][k0] || S[i][j][k][k0 - 1];
}
int sum;
re(i, n) {
D[i] = 0;
re2(j, i, n) {sum = 0; re(k, m) if (A[j][k]) sum++; if (sum) D[i] += sum - 1;}
re(k, m) {sum = 0; re2(j, i, n) if (A[j][k]) sum++; if (sum) D[i] += sum - 1;}
}
}
void dfs1(int No, int v, int sum)
{
if (sum + D[No + 1] >= res) return;
if (v == len[No] + 1) dfs0(No + 1, 0, sum, 1); else if (tmp[No][v] != 1) dfs1(No, v + 1, sum); else {
int l, r, sum0 = sum;
if (v) l = pos[No][v - 1] + 1; else l = 0;
if (v == len[No]) r = m - 1; else r = pos[No][v];
re3(j, l, r) R[No][j] = 0; dfs1(No, v + 1, sum);
re3(j, l, r) {R[No][j] = 1; sum0++;} dfs1(No, v + 1, sum0);
}
}
void dfs0(int No, int v, int sum, bool FF)
{
if (sum + D[No + 1] >= res) return;
bool FF0; if (A[No][v]) {if (!FF) return; else FF0 = 0;} else FF0 = FF;
if (v == m - 1) {
if (No == n - 1) {
len[No] = 0; re(i, m-1) if (C[No][i]) pos[No][len[No]++] = i;
int l, r, x; bool FFF = 1;
re3(i, 0, len[No]) {
if (i) l = pos[No][i - 1] + 1; else l = 0;
if (i == len[No]) r = m - 1; else r = pos[No][i];
x = 0; rre(j, No) if (R[j][l]) {x = j + 1; break;}
if (!S[x][l][No][r]) {FFF = 0; break;}
}
if (FFF) res = sum;
return;
}
len[No] = 0; re(i, m-1) if (C[No][i]) pos[No][len[No]++] = i;
int l, r, x, sum0 = sum;
re3(i, 0, len[No]) {
if (i) l = pos[No][i - 1] + 1; else l = 0;
if (i == len[No]) r = m - 1; else r = pos[No][i];
x = 0; rre(j, No) if (R[j][l]) {x = j + 1; break;}
if (S[x][l][No][r] && S[No + 1][l][No + 1][r]) {
tmp[No][i] = 2; re3(j, l, r) {sum0++; R[No][j] = 1;}
} else if (S[x][l][No][r]) {
tmp[No][i] = 1; re3(j, l, r) R[No][j] = 0;
} else {
tmp[No][i] = 0; re3(j, l, r) R[No][j] = 0;
}
}
dfs1(No, 0, sum0);
} else if (No && (!R[No - 1][v] || !R[No - 1][v + 1])) {
if (C[No - 1][v]) {C[No][v] = 1; dfs0(No, v + 1, sum + 1, 1);} else {C[No][v] = 0; dfs0(No, v + 1, sum, FF0);}
} else {
C[No][v] = 0; dfs0(No, v + 1, sum, FF0);
C[No][v] = 1; dfs0(No, v + 1, sum + 1, 1);
}
}
void pri()
{
printf("%d\n", res);
}
int main()
{
init();
prepare();
dfs0(0, 0, 0, 1);
pri();
return 0;
}