这题目不会做，看了网上别人写的代码，发现使用DFS+剪枝完成，
把火柴看成一个集合A，把正方形看成集合B，火柴在正方形上，就连边，然后就用最少的火彩覆盖所有B的正方形，果断DFS，但有剪枝，1.按在正方形数多 从大到小排序。
2.去掉效果一样的火柴。
3.judge下，看后面火柴全取到不到的了res，不行就剪掉。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Stick
{
int sum;
long long sq;
bool status;
friend int operator<(Stick a,Stick b)
{
return a.sum>b.sum;
}
}stick[62];
int n,k,deletenum;
long long fna;
int pos[]={0,0,25,41,50,54,55};
long long res[6];
const int INF=9999999;
int minn;
void build(int row,int col,int index,int flag,int size)
{
if(row<=0||row+size>n+1||col<=0||col+size>n+1)
return;
if(flag)//如果是列火柴就颠倒判断。
{
int temp=row;
row=col;
col=temp;
}
int lo=(row-1)*(n-size+1)+col;
int pt=pos[size]+lo;
long long temp=1;
temp<<=(pt-1);
stick[index].sq|=temp;
stick[index].sum++;
}
void link()
{
int flag,row,col;
for(int i=1;i<=2*n*(n+1);i++)
{
if((i-1)%(2*n+1)<n)
{
flag=0;
col=i%(2*n+1);
row=(i-1)/(2*n+1)+1;
}
else
{
flag=1;
col=(i-1)/(2*n+1)+1;
row=(i-1)%(2*n+1)-n+1;
}
for(int size=1;size<=n;size++)
for(int k=col-size+1;k<=col;k++)
{
build(row-size,k,i,flag,size);
build(row,k,i,flag,size);
}
}
}
void deletee()
{
for(int i=1;i<=2*n*(n+1);i++)
{
if(stick[i].sum==-1)
continue;
long long temp=stick[i].sq|fna;
for(int j=i+1;j<=2*n*(n+1);j++)
if(temp==(stick[j].sq|fna))//剪掉效果一样的j,注意一定加括号，==优先级明显高于|
{
deletenum++;
stick[j].sum=-1;
}
}
}
void finish()//完成的状态
{
res[1]=1;
res[2]=(((long long)1<<25)|15);
res[3]=((long long)1<<9)-1;
res[3]|=((long long )15<<25);
res[3]|=((long long)1<<41);
res[4]=(((long long )1<<16)-1);
res[4]|=((((long long)1<<9)-1)<<25);
res[4]|=(long long)15<<41;
res[4]|=(long long)1<<50;
res[5]=(1<<55)-1;
}
int op(int x)
{
long long temp=fna;
for(int i=x;i<=2*n*(n+1)-deletenum;i++)
temp|=stick[i].sq;
if(temp!=res[n])
return 1;
return 0;
}
void dfs(int x,int count)
{
//printf("%d\n",x);
if(x>2*n*(n+1)-deletenum||count>=minn||op(x))
return;
long long instead=fna;//DFS里面的temp值一定要是自动变量，否则深搜会改变，
if(stick[x].status==0)
{
fna|=stick[x].sq;
if(fna==res[n])
{
if(count+1<minn)
minn=count+1;
fna=instead;
return;
}
dfs(x+1,count+1);
fna=instead;//变回来，回溯
}
dfs(x+1,count);
}
int main()
{
int n1;
finish();
//for(int i=1;i<=5;i++)
//printf("%lld\n",res[i]);
while(scanf("%d",&n1)==1)
{
fna=0;
while(n1--)
{
minn=INF;
memset(stick,0,sizeof(stick));
scanf("%d%d",&n,&k);
fna=0;
link();
for(inti=1;i<=k;i++)
{
int a;
scanf("%d",&a);
stick[a].status=1;
fna|=stick[a].sq;
}
deletenum=0;
deletee();
//printf("%d\n",deletenum);
sort(stick+1,stick+2*n*(n+1)+1);
dfs(1,0);
//for(int i=1;i<=12;i++)
//printf("%lld\n",stick[i].sq);
printf("%d\n",minn);
}
}
return 0;
}