書上已經(jīng)講得很清楚了 主要是拿什么數(shù)據(jù)結(jié)構(gòu)表示的問題
這道題跟萬圣節(jié)移動(dòng)幾個(gè)小鬼的問題i一樣要處理一下
就是要用一個(gè)二維數(shù)組表示 array [num ] [stick] 第num個(gè)東西有stick的成分
比如G[num][dir]表示num個(gè)格子上有dir的移動(dòng)方式
這題是contains[num][side] = 1表示第num個(gè)正方形有第side的棒子
然后就是算法了 有這個(gè)數(shù)組自然會(huì)去表示現(xiàn)在這個(gè)狀態(tài)第num個(gè)方形上有幾個(gè)棍子（或者說他是不是方形）也就是size[num] = sticks 第num方形有sticks火柴
有這幾個(gè)東西自然就知道要先做預(yù)處理 枚舉一下方形的坐標(biāo)統(tǒng)計(jì)
然后是暴力的搜索 每次選最小的方形選擇一個(gè)火柴去破壞 前面已經(jīng)講了這個(gè)火柴怎么表達(dá)了 然后搜索就行
我自己合上書寫的時(shí)候犯了兩個(gè)小錯(cuò) 一直tle 查了一段時(shí)間
首先 剪枝 找到一個(gè)答案就可以設(shè)為最佳 比這個(gè)答案層數(shù)更多的就不要dfs了
還有就是預(yù)處理的時(shí)候順序有點(diǎn)問題 print出來就好了

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxs = 60;
const int maxm = 60;
int ans;
int square, n, k;                                             //square拆解之前所有可能的正方形數(shù)目 
int contains[maxs][maxm], size[maxs], fullsize[maxs];         //contain[ num ][ stick] 第num個(gè)正方形有編號(hào)為第stick根的棒子組成 
int stick[maxm];


void init(){
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= 2*n*(n+1); i++) stick[i] = 1;                    //初始化順序 
    while(k--){
        int v;
        scanf("%d", &v);
        stick[v] = 0;
    }
//printf("test\n");
//for(int i = 1; i < 2*n*(n+1); i++) printf("%d ", stick[i]);
//printf("%d\n", stick[2*n*(n+1)]);
    square = 0;
    memset(contains, 0, sizeof(contains));
    for(int len = 1; len <= n; len++){
        for(int x = 0; x <= n-len; x++){
            for(int y = 0; y <= n-len; y++){
                size[square] = 0;
                fullsize[square] = 4*len;
                for(int j = 1; j <= len; j++){
                    int up = (2*n+1)*y+x+j;
                    int down = (2*n+1)*(y+len)+x+j;
                    int left = (2*n+1)*(y+j)+x-n;
                    int right = (2*n+1)*(y+j)+x+len-n;
                    contains[square][up] = 1;
                    contains[square][down] = 1;
                    contains[square][left] = 1;
                    contains[square][right] = 1;
//                  if(len == 2){
//                      printf("x %d y %d j %d",x,y,j);
//                      printf(" up %d  down %d left %d right %d\n",up,down,left,right);
//                  }
                    size[square] += stick[up] + stick[down] + stick[left] + stick[right];
                }
                square++;
            }
        }
    }
//for(int i = 0; i < square; i++){
//  if(size[i] == fullsize[i]){
//      printf("%d\n",i);
//          for(int j = 1; j <= 2*n*(n+1); j++){
//              printf("%d ", contains[i][j]);
//          }
//      printf("\n");       
//  }
//}
//for(int i = 0; i < square; i++){
//  printf("%d ",size[i]);
//}
}
int count(){
    for(int s = 0; s < square; s++){
        if(size[s] == fullsize[s]) return s;
    }
    return -1;
}
void dfs(int dep){
    if(dep>ans) return;            //剪枝 
    
    int flag = count();
    if(flag == -1){
        ans = min(dep, ans);
        return;
    }//else{
        for(int s = 1; s <= 2*n*(n+1); s++){
            if(contains[flag][s]){
                for(int i = 0; i < square; i++){
                    if(contains[i][s]) size[i]--;
                }
                dfs(dep+1);
                for(int i = 0; i < square; i++){
                    if(contains[i][s]) size[i]++;
                }
            }
        }
//  }
}

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        init();
        ans = n*n;
        dfs(0);
        printf("%d\n",ans);
    }
    return 0;
}