【題意】
下圖左側顯示了一個用24根火柴棍構成的完整3×3網格。
所有火柴的長度都是1。
您可以在網格中找到許多不同大小的正方形。
在左圖所示的網格中，有9個邊長為1的正方形，4個邊長為2的正方形和1個邊長為3的正方形。
組成完整網格的每一根火柴都有唯一編号，該編号從上到下，從左到右，從1開始按順序配置設定。
如果你将一些火柴棍從完整網格中取出，形成一個不完整的網格，則一部分正方形将被破壞。
右圖為移除編号12,17和23的三個火柴棍後的不完整的3×3網格。
這次移除破壞了5個邊長為1的正方形，3個邊長為2的正方形和1個邊長為3的正方形。
此時，網格不具有邊長為3的正方形，但仍然具有4個邊長為1的正方形和1個邊長為2的正方形。
現在給定一個（完整或不完整）的n×n（n不大于5）網格，求至少再去掉多少跟火柴棒，可以使得網格内不再含有任何尺寸的正方形。
【輸入格式】
輸入包含T組測試用例。
測試用例的數量T在輸入檔案的第一行中給出。
每個測試用例由兩行組成：
第一行包含一個整數n，表示網格的規模大小。
第二行以非負整數k開頭，表示所給網格相較完整的n×n網格所缺少的火柴杆數量，後跟k個整數表示所有缺少的火柴杆的具體編号。
注意，如果k等于零，則表示輸入網格是完整的n×n網格。
【輸出格式】
每個測試用例輸出一個結果，表示破壞所有正方形，所需的去掉火柴棒的最小數量。
每個結果占一行。
【輸入樣例】
2
2
3
3 12 17 23
【輸出樣例】
3
3
這是一道非常繁瑣的題目。難點是火柴的編号處理和圖形的處理。
為了友善，我們用兩種坐标(x,y)定位每根火柴的位置。
如圖是3*3的網格的火柴的x坐标。
可以發現，x坐标為奇數則火柴為橫的，否則為豎的。
類似的，y坐标如下。
可以發現，y坐标為偶數則火柴為橫的，否則為豎的。
//樸素版編号
s=2*n+1;tot=0;
for(int i=1;i<=s;i++)
for(int j=1;j<=s;j++)
if((i&1)!=(j&1))id[i][j]=++tot;//一根火柴的x，y坐标的奇偶性必然不同
//不用判斷的方法
s=2*n+1;tot=0;
for(int i=1;i<=s;i++)
for(int j=-(!(i&1))+2;j<=s;j+=2)
id[i][j]=++tot;
接下來，我們定義兩個二維數組（vector實作）e，g，分别表示火柴所屬的正方形的編号，正方形所圍成的火柴的編号。
給正方形編号
正方形邊的坐标。
可以發現，如果我們先枚舉i,j,len(邊長)i,j,len(邊長)i,j,len(邊長).
那麼左邊的邊的編号的橫坐标每次增加2.
右邊的邊的編号的縱坐标比對應位置多2∗len−12*len-12∗len−1
上邊的邊的編号的縱坐标每次增加2.
下面的邊的編号的橫坐标比對應位置多2∗len−12*len-12∗len−1
為了使正方形大小單調遞增。
我們先枚舉aaa,表示2∗len−12*len-12∗len−1.（即正方形的規模）
再枚舉兩個偶數i,ji,ji,j.
最後枚舉[0,a)[0,a)[0,a)的偶數即可。
tot=0;
for(int a=1;a<s;a+=2)//規模——a/2是邊長。
for(int i=2;i+a<=s;i+=2)//豎邊
for(int j=2;j+a<=s;j+=2) {//橫邊
++tot;
for(int x=0;x<a;x+=2) {
e[id[x+i][j-1]].push_back(tot);//left
e[id[x+i][j+a]].push_back(tot);//right
e[id[i-1][x+j]].push_back(tot);//up
e[id[i+a][x+j]].push_back(tot);//down
g[tot].push_back(id[x+i][j-1]);
g[tot].push_back(id[x+i][j+a]);
g[tot].push_back(id[i-1][x+j]);
g[tot].push_back(id[i+a][x+j]);
}
}
以上我們講完了最難了解的編号問題。
最後，dfs即可。dfs架構為：每次找出最小的正方形，并對其一條邊進行删除。
再輔以估價函數，可以跑得更快。
代碼：
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=65;
int n,k,s,tot,tmp,id[13][13],dep;
vector<int>e[N],g[N],empty;
bool v[N];
int gj() {
bool w[N];memcpy(w,v,sizeof w);
int ans=0;
for(int i=1;i<=tot;i++) {//把每個正方形的所有邊都删除，單隻算删除一次。
if(w[i]) {
if(!ans)tmp=i;//最小正方形。
++ans;
for(int j=0;j<g[i].size();j++)//枚舉出每一條邊
for(int x=0;x<e[g[i][j]].size();x++)//把邊對應的正方形删掉。
w[e[g[i][j]][x]]=0;
}
}
return ans;
}
bool dfs(int now) {
int cnt=gj();
if(!cnt)return 1;
if(now+cnt>dep)return 0;
bool w[N];memcpy(w,v,sizeof w);
int tmp0=tmp;
for(int i=0;i<g[tmp0].size();i++) {//枚舉最小正方形的邊
int st=g[tmp0][i];
for(int j=0;j<e[st].size();j++)//删除邊——這些正方形都不可以用了
v[e[st][j]]=0;
if(dfs(now+1))return 1;
memcpy(v,w,sizeof v);
}
return 0;
}
void solve() {
scanf("%d%d",&n,&k);
s=2*n+1;tot=0;
for(int i=1;i<=s;i++)
for(int j=-(!(i&1))+2;j<=s;j+=2)
id[i][j]=++tot;
for(int i=1;i<=tot;i++)e[i]=empty;
tot=n*(n+1)*s/6;
for(int i=1;i<=tot;i++)g[i]=empty;
tot=0;
for(int a=1;a<s;a+=2)//規模——a/2是邊長。
for(int i=2;i+a<=s;i+=2)//豎邊
for(int j=2;j+a<=s;j+=2) {//橫邊
++tot;
for(int x=0;x<a;x+=2) {
e[id[x+i][j-1]].push_back(tot);//left
e[id[x+i][j+a]].push_back(tot);//right
e[id[i-1][x+j]].push_back(tot);//up
e[id[i+a][x+j]].push_back(tot);//down
g[tot].push_back(id[x+i][j-1]);
g[tot].push_back(id[x+i][j+a]);
g[tot].push_back(id[i-1][x+j]);
g[tot].push_back(id[i+a][x+j]);
}
}
memset(v,1,sizeof v);
while(k--) {
int a;scanf("%d",&a);
for(int i=0;i<e[a].size();i++)
v[e[a][i]]=0;
}
dep=0;
while(!dfs(0))dep++;
printf("%d
",dep);
}
int main() {
int T;scanf("%d",&T);
while(T--)solve();
return 0;
}