分享一个能过的代码
原作者:https://www.bbsmax.com/A/WpdKLagXzV/
#include<bits/stdc++.h>
using namespace std;
const int INFS = 0x7fffffff;
int N,C,E,bound;
long long squ[100],xiao[6][6];
bool flag;
long long get2(int i){return ((long long)1<<(i-1));}
int getnumber1(int i,int j){return (2*N+1)*(i-1)+j;}
int getnumber2(int i,int j){return (2*N+1)*(i-1)+j+N;}
void build(){
C=0;
memset(xiao,0,sizeof(xiao));
int i,j;
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
{
xiao[i][j]|=get2(getnumber1(i,j))|get2(getnumber1(i+1,j));
xiao[i][j]|=get2(getnumber2(i,j))|get2(getnumber2(i,j+1));
squ[C++]=xiao[i][j];
}
for(int size=2;size<=N;size++){
for(i=1;i+size-1<=N;i++){
for(j=1;j+size-1<=N;j++){
squ[C]=0;
for(int a=0;a<size;a++){
for(int b=0;b<size;b++){
squ[C]^=xiao[i+a][j+b];
}
}
C++;
}
}
}
}
int dfs(long long state,int de){
int h=0;
long long u=0,s=state;
for(int i=0;i<C;i++){
if((s&squ[i])==squ[i]){
h+=1;
s^=squ[i];
if(u==0)
u=squ[i];
}
}
if(h==0){
flag=true;
return de;
}
if(de+h>bound)
return de+h;
int news=INFS;
for(int i=1;i<=E;i++){
if(u&get2(i)){
int b=dfs(state^get2(i),de+1);
if(flag)
return b;
news=min(b,news);
}
}
return news;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d",&N);
build();
E=2*N*(N+1);
int k;
long long state=((long long)1<<E)-1;
scanf("%d",&k);
for(int i=0;i<k;i++){
int x;
scanf("%d",&x);
state^=get2(x);
}
flag=false;
bound=0;
while(!flag){
bound=dfs(state,0);
}
printf("%d\n",bound);
}
}