题意：

给定一个火柴棒拼成的方格阵，然后去掉一些火柴棒，问至少再去掉几根火柴棒能够让图中一个正方形都没有。

思路：

1. 由于题目中给定了 n 的范围，2 * n * (n + 1) <= 60 -> 所以能够保证所有的火柴用 __int64 的位运算表示;

2. 问题的关键在于如何生成火柴构成的方阵，以及生成方阵之后如何去搜索;

3. 启发式函数 h 的计算需要考量：如果删除了某个方阵的一个边，则能够保证 h(s1) <= h(s2) + C(s1, s2)，其中 C(s1, s2) = 1，h(s1) - h(s2) <= 1，可以用反证法证明;

4. 各种位运算的范围要明确，如 1<

紫书分析：迭代加深搜索为主算法框架，搜索对象有两种，

1.每次考虑一个没有被破坏的正方形，在边界上找一根火柴拿掉，搜索对象是正方形，应先考虑小正方形，在考大打正方形，因为小正方形被破坏之后，大正方形就被破坏了，但是反过来却不一定，还可以加入最优性减枝，即把每个正方形看成一个顶点，有公共火柴的正方形连城一条边，则每个连通分量至少拿走一根火柴。

2.每次找一个至少能破坏一个正方形的火柴，然后拿掉。搜索对象是火柴，应该搜索尽量能破坏最多正方形的火柴，这需要计算出考虑每根火柴可以破坏掉多少个正方形，从小到大排序d[1],...当d[1]为1时即可停止搜索，因为此时可以直接计算出还需要的火柴个数，这个d数组也可以用于最优性减枝，找到最小的i，使得d[1]+d[2]=...+d[i]<=k（其中k为还省得正方形个数），至少还要i跟火柴。

还能用DLX算法解决。

?

#include
   
     #include
    
      #include
     
       #include
      
        using namespace std; const int INFS = 0x7fffffff; int N,C,E,bound; __int64 square[100], base[6][6]; bool succ; inline int __int64 getflag(int i){ return ((__int64)1<<(i-1)); } inline int geth(int i,int j){ return (2*N+1)*(i-1)+j; } inline int getv(int i,int j){ return (2*N+1)*(i-1)+j+N; } void build() { C=0; memset(base,0,sizeof(base)); for(int i=1;i<=N;i++){ for(int j=1;j<=N;j++){ base[i][j] |= getflag(geth(i,j)) | getflag(geth(i+1,j)); base[i][j] |= getflag(getv(i,j)) | getflag(getv(i,j+1)); square[C++] = base[i][j]; } } for(int size=2;size<=N;size++){ for(int i=1;i+size-1 <= N;i++){ for(int j=1;j+size-1<=N;j++){ square[C]=0; for(int a=0;a
       
        bound){ return depth+h; } int newbound = INFS; for(int i=1;i<=E;i++){ if(u & getflag(i)){ int b=dfs(state ^ getflag(i),depth+1); if(succ) return b; newbound = min(b,newbound); } } return newbound; } int main() { int cases; scanf("%d",&cases); while(cases--){ scanf("%d",&N); build(); E = 2*N*(N+1); int k; __int64 state = ((__int64)1<
        
         
?