정사각형 파괴

책 에서 분명히 말 했 듯 이 주로 어떤 데이터 구 조 를 가지 고 문 제 를 나타 내 는 지 이 문 제 는 할 로 윈 에 임 프 몇 명 을 이동 시 키 는 문제 i 와 같이 처리 해 야 한다. 즉, 하나의 2 차원 배열 로 array [num] [stick] 제 num 의 물건 에 stick 성분 이 있다. 예 를 들 어 G [num] [dir] 표 시 는 num 의 칸 에 dir 의 이동 방식 이 있다 는 것 이다. 이 문 제 는 contains [num] [side] 이다.= 1. num 의 정사각형 에 side 의 막대기 가 있다 는 뜻 이 고 그 다음 에 알고리즘 이 있 습 니 다. 이 배열 이 있 으 면 자 연 스 럽 게 현재 이 상태 에서 num 의 사각형 에 막대기 가 몇 개 있다 는 뜻 입 니 다.= sticks num 사각형 에 sticks 성냥 이 있 습 니 다. 이 몇 가지 가 있 으 면 자 연 스 럽 게 알 수 있 습 니 다.먼저 가 지 를 잘라 서 답 을 찾 으 면 가장 좋 은 것 으로 설정 할 수 있 습 니 다.

#include 
#include 
#include 
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
");
//for(int i = 1; i < 2*n*(n+1); i++) printf("%d ", stick[i]);
//printf("%d
", 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
",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
",i);
//          for(int j = 1; j <= 2*n*(n+1); j++){
//              printf("%d ", contains[i][j]);
//          }
//      printf("
");       
//  }
//}
//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
",ans);
    }
    return 0;
}