uva1603 破坏正方形

书上已经讲得很清楚了 主要是拿什么数据结构表示的问题
这道题跟万圣节移动几个小鬼的问题i一样要处理一下
就是要用一个二维数组表示 array [num ] [stick] 第num个东西有stick的成分
比如G[num][dir]表示num个格子上有dir的移动方式
这题是contains[num][side] = 1表示第num个正方形有第side的棒子
然后就是算法了 有这个数组自然会去表示现在这个状态第num个方形上有几个棍子（或者说他是不是方形）也就是size[num] = sticks 第num方形有sticks火柴
有这几个东西自然就知道要先做预处理 枚举一下方形的坐标统计
然后是暴力的搜索 每次选最小的方形选择一个火柴去破坏 前面已经讲了这个火柴怎么表达了 然后搜索就行
我自己合上书写的时候犯了两个小错 一直tle 查了一段时间
首先 剪枝 找到一个答案就可以设为最佳 比这个答案层数更多的就不要dfs了
还有就是预处理的时候顺序有点问题 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拆解之前所有可能的正方形数目 
int contains[maxs][maxm], size[maxs], fullsize[maxs];         //contain[ num ][ stick] 第num个正方形有编号为第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;
}