acwing182-破坏正方形
算法:IDA*
时间复杂度:(指数)
题目描述&数据范围:下图左侧显示了一个用24根火柴棍构成的完整3×3网格。所有火柴的长度都是1。您可以在网格中找到许多不同大小的正方形。在左图所示的网格中，有9个边长为1的正方形，4个边长为2的正方形和1个边长为3的正方形。组成完整网格的每一根火柴都有唯一编号，该编号从上到下，从左到右，从1开始按顺序分配。如果你将一些火柴棍从完整网格中取出，形成一个不完整的网格，则一部分正方形将被破坏。
右图为移除编号12,17和23的三个火柴棍后的不完整的3×3网格。这次移除破坏了5个边长为1的正方形，3个边长为2的正方形和1个边长为3的正方形。此时，网格不具有边长为3的正方形，但仍然具有4个边长为1的正方形和1个边长为2的正方形。现在给定一个（完整或不完整）的n×n（n不大于5）网格，求至少再去掉多少根火柴棒，可以使得网格内不再含有任何尺寸的正方形。(n<=5)
做法分析:由于题意是要让所有正方形都不完整.那么,我们先计算下正方形的个数,我们很容易发现边长为5的正方形个数是1^2+2^2+...+5^2=1+4+9+16+25=55..然后边数数下发现是60,我们姑且开65hhh.计算完正方形的个数后,题目要求我们拆最少的木棍破坏掉所有正方形也就是对于每个正方形都需要掉至少一根木棍.我们先把每个正方形所需的木棍存起来,然后把去掉的木棍标记,然后用IDA*来求最小的操作步数.下面细节全部放代码里了--搜索就是细节多,会给大家打注释的.

#include <bits/stdc++.h>
using namespace std;
const int N=65;
int k;
vector<int>v[N];//记录每个正方形的每条边
bool st[N];

bool ck(int x)
{
    for(int i=0;i<v[x].size();i++)
    {
        if(st[v[x][i]]) return false;//只要不完整
    }
    return true;//只要完整
}

int f()
{
    int cnt=0;
    bool state[N];
    memcpy(state,st,sizeof st);
    for(int i=0;i<k;i++)
    {
        if(ck(i))
        {
            for(int j=0;j<v[i].size();j++)
            {
                st[v[i][j]]=true;
            }
            cnt++;
        }
    }
    memcpy(st,state,sizeof state);
    return cnt;
}

bool dfs(int dep,int max_dep)
{
    if(dep+f()>max_dep) return false;
    for(int i=0;i<k;i++)//枚举每个正方形
    {
        if(ck(i))//假如这个正方形是完整的,那就枚举拆哪条边.
        {
            for(int j=0;j<v[i].size();j++)
            {
                st[v[i][j]]=true;//拆了这条边.
                if(dfs(dep+1,max_dep)) return true;
                st[v[i][j]]=false;//恢复现场
            }
            return false;
        }
    }
    return true; 
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        memset(st,false,sizeof st);//由于是T组数据,所以赋值为false.
        int n,m,d;k=0;
        cin>>n;
        d=2*n+1;//每行相差d距离
        for(int len=1;len<=n;len++)//枚举长度.
        {
            for(int x=0;x+len<=n;x++)//枚举横坐标起点.
            {
                for(int y=0;y+len<=n;y++)//枚举纵坐标起点.
                {
                   v[k].clear();
                   for(int i=1;i<=len;i++)//进行操作
                   {
                       v[k].push_back(x*d+i+y);//上
                       v[k].push_back((x+len)*d+i+y);//下
                       v[k].push_back((i-1+x)*d+n+y+1);//左
                       v[k].push_back((i-1+x)*d+n+y+1+len);//右
                   }
                   k++;
                }
            }
        }
        cin>>m;
        while(m--)
        {
            int x;cin>>x;
            st[x]=true;//把这些边标记为去掉了
        }
        int depth=0;
        while(!dfs(0,depth)) depth++;
        cout<<depth<<endl;
    }
    return 0;
}