算法

(IDA*, DFS) $O(指数)$

先将每个正方形的所有边的编号预处理出来。

• 这一部分要耐心观察原图形找规律，可以发现每个正方形上下两组边是公差为1的等差数列，只要求出数列的首项即可；左右两组边是公差为 $2n + 1$ 的等差数列，同理求出首项即可。

然后问题变成最少选出多少边，使得每个正方形中至少被选出一条边。
这是一个经典的重复覆盖问题，可以用 Dancing Links 求解。

这里我们不适用DLX这个数据结构，直接求解。

估计函数：

• 枚举所有未被删掉的正方形，将其所有边全部删掉，只记删除一条边。这样估计出的值一定不大于真实值，满足IDA*对估价函数的要求。其实这也是Dancing Links求解重复覆盖问题时的估价函数。

搜索顺序优化：

• 找出最小的未被删除的正方形，依次枚举删除每条边。

时间复杂度

搜索空间是指数级别的，但由于启发函数和剪枝的存在，实际搜索到的状态较少。

C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int N = 61;

int n, m;
bool st[N];
vector<int> square[N];

bool check(vector<int> &sq)
{
    for (auto x : sq)
        if (st[x])
            return false;
    return true;
}

int f()
{
    static bool state[N];
    memcpy(state, st, sizeof st);

    int res = 0;
    for (int i = 0; i < m; i ++ )
    {
        auto &sq = square[i];
        if (check(sq))
        {
            res ++ ;
            for (auto x : sq) st[x] = true;
        }
    }

    memcpy(st, state, sizeof st);

    return res;
}

bool dfs(int depth)
{
    if (f() > depth) return false;

    for (int i = 0; i < m; i ++ )
    {
        auto &sq = square[i];
        if (check(sq))
        {
            for (auto x : sq)
            {
                st[x] = true;
                if (dfs(depth - 1)) return true;
                st[x] = false;
            }
            return false;
        }
    }

    return true;
}

main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d", &n);

        m = 0;
        for (int i = 1; i <= n; i ++ )
            for (int a = 1; a + i - 1 <= n; a ++ )
                for (int b = 1; b + i - 1 <= n; b ++ )
                {
                    square[m].clear();
                    for (int j = 0; j < i; j ++ )
                    {
                        int d = 2 * n + 1;
                        square[m].push_back((a - 1) * d + b + j);
                        square[m].push_back((a - 1 + i) * d + b + j);
                        square[m].push_back(n + 1 + (a - 1) * d + b - 1 + j * d);
                        square[m].push_back(n + 1 + (a - 1) * d + b - 1 + j * d + i);
                    }
                    m ++ ;
                }

        memset(st, 0, sizeof st);
        int k;
        scanf("%d", &k);
        for (int i = 0, t; i < k; i ++ )
        {
            scanf("%d", &t);
            st[t] = true;
        }

        int depth = 0;
        while (!dfs(depth)) depth ++ ;

        printf("%d\n", depth);
    }

    return 0;
}