题目描述
下图左侧显示了一个用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的正方形。
样例
输入样例:
2
2
0
3
3 12 17 23
输出样例:
3
3
算法1
(IDA*)
题意:至少去掉多少根木棒,使得所有正方形都被破坏 <-> 至少选择多少条边,使得每个正方都有一条边被选中(破坏)。
需要注意:四条边push到vector
数组中,详情见抽风题解
估价函数:
- 我们可以在每个没被破坏的正方形上将其所有边破坏,然后将删除的边数记为1. 这样得到的估计值肯定小于真实值。
注意dfs(depth)
递归, {IDA*}的另外一种写法。递归的时候dfs(depth - 1)
,终止条件if (f() > depth) return false;
, 其实是把 if (depth + f()) > max_depth
中的参数depth
和max_depth
合二为一。单独交给递归管理。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
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;
}
//IDA*
bool dfs(int depth){//注意这里跟普通的写法不一样,直接将max_depth单独作为参数,因此每次递归dfs(depth - 1).
if (f() > depth) return false;
for (int i = 0; i < m; i ++ ){//枚举所有正方形
auto &sq = square[i];
if (check(sq)){//如果第i个正方形没有被破坏
for (auto x: sq){//把每一个边都破坏
st[x] = true;
if (dfs(depth - 1)) return true;
st[x] = false;
}
return false;
}
}
return true;
}
int 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 ++ ){ //true表示当前边已经被破坏
scanf("%d", &t);
st[t] = true;
}
int depth = 0;
while (!dfs(depth)) depth ++;
printf("%d\n", depth);
}
return 0;
}