算法
(IDA*, DFS) $O(指数)$
先将每个正方形的所有边的编号预处理出来。
- 这一部分要耐心观察原图形找规律,可以发现每个正方形上下两组边是公差为1的等差数列,只要求出数列的首项即可;左右两组边是公差为 $2n + 1$ 的等差数列,同理求出首项即可。
然后问题变成最少选出多少边,使得每个正方形中至少被选出一条边。
这是一个经典的重复覆盖问题,可以用 Dancing Links 求解。
这里我们不适用DLX这个数据结构,直接求解。
估计函数:
- 枚举所有未被删掉的正方形,将其所有边全部删掉,只记删除一条边。这样估计出的值一定不大于真实值,满足IDA*对估价函数的要求。其实这也是Dancing Links求解重复覆盖问题时的估价函数。
搜索顺序优化:
- 找出最小的未被删除的正方形,依次枚举删除每条边。
时间复杂度
搜索空间是指数级别的,但由于启发函数和剪枝的存在,实际搜索到的状态较少。
C++ 代码
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
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;
}
dfs里面,第二个return false剪枝给忘了就t了,不加引用也给t了,这题卡的挺紧的,orz
y总第二个return false剪枝我不太明白,能讲解下吗
如果发现某个正方形无法被破坏,那么一定无解,直接返回false。
懂了懂了
bool check(vector[HTML_REMOVED] &sq) 这里 为什么是&sq而不是直接sq
auto那几个引用可真细节啊,不加给T了....
这里不加的话会把整个数组copy一遍,会很慢。
引用和引用变量的赋值数是同一个地址空间