poj 1084 Square Destroyer 搜索剪枝

缘起

日常浪费生命~ poj 1084 Square Destroyer

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
有一个由火柴棒组成的N*N（1<=N<=5）的格子. 按照下图给火柴棒编号，
将移除某些火柴棒后的状态作为初始状态, 
需要再移除一些火柴棒以保证图中一个正方形都没有.
请计算出最少需要移除几根火柴棒

【输入】
多样例. 首先给出样例数. 然后每个样例先给出N. 然后是已经移除的火柴棒的数量k. 然后是k个数字表示移除的火
柴棒

【输出】
对于每个样例, 输出最少要移除几根火柴棒

【样例输入】
2
2
0
3
3 12 17 23

【样例输出】
3
3

【限制】
1s

说明:

样例2如下图所示

本题N比较小, 考虑使用搜索. 但是一共不超过 (N+N+1)*N+N=2*N*(N+1)<=60 根火柴棒. 初始状态有不超过 N^2+1个正方形（外面还有一个大的）需要等我们去破坏(每个都需要破坏).

所以其实就是找出这不超过60根火柴棒的最少数量的子集让这正方形集合全部破坏. 而枚举这些子集的代价是2^(2n(n+1)) 可能到达2^60, 这种复杂度是我们不能接受的. 显然是需要剪枝的. 但是没有太明显的剪枝条件. 此时就要快速能求出一组解. 然后用解本身去作为剪枝条件。

首先，开一个(N^2+1个元素的)哈希数组表示每个正方形是否已经被破坏.

然后考察这2N(N+1)根火柴棒, 每根火柴棒它属于的完整正方形的数量. 将这些火柴棒按照属于完整正方形的数量降序排序. 即我们优先考虑能破坏最多完整正方形的火柴棒（因为我们需要能快速求出一组解）. 而且dfs的时候先进行”去掉”的递归，而不是”保留” 的递归. 这样也都是为了能快速得到一组解.

而且本题还有一个考察点就是火柴棒的编号和它属于哪几个正方形之间的对应关系. 其实就看它的编号除以(2N+1)的余数和商. 具体见代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL

int n,k,remain,ans,nn,nnn; // remain是伊始剩下的正方形数量
bool v[100]; // v[i]表示编号为i的正方形是否存在,true表示存在

struct Stick // 火柴棒的数据结构
{
	int index; // 该火柴棒的编号
	int belong; // 该火柴棒属于多少个正方形
	int square[60]; // square[0,...,belong-1]是该火柴棒属于的正方形
	bool initexist; // true表示初始状态是存在的
	bool operator <(Stick o)
	{
		return belong>o.belong; // 属于越多的正方形,排在越前面, 越先被考察
	}
}s[100];

void init()
{
	ans = 0x3f3f3f3f;
	nn = n*(n+1)*(2*n+1)/6;
	nnn = 2*n*(n+1);
	memset(v, true, sizeof(v)); // 伊始所有的正方形都是存在的
	remain = nn; // 总共有1^2+2^2+...+n^2个正方形
	for (int i = 1; i<=nnn;i++)
	{
		s[i].index = i;
		s[i].initexist = true;
		s[i].belong = 0;
	}
	for (int i = 1; i<=n; i++) // 枚举正方形的边长,正方形的编号是从边长为1的开始(n^2个), 然后是变长为2的正方形((n-1)^2个),...,边长为n的正方形,一共1个
	{
		for (int j = 1; j<=n-i+1; j++)
		{
			for (int k = 1,num,t; k<=n-i+1; k++) // 枚举正方形的左上角（j,k）
			{
				num = nn-(n-i+1)*(n-i+2)*(2*n-2*i+3)/6+(j-1)*(n-i+1)+k; // 正方形的编号num, 它是一个左上角(j,k)边长为i的正方形
				for (int x = 0; x<i; x++) 
				{
					t = (j-1)*(2*n+1)+k+x; // 第一条边 (j,k)->(j, k+i), 每一段是(j, k+x)到(j, k+x+1)
					s[t].square[s[t].belong++] = num; // t号火柴棒参与了num这个正方形的构建
					t = (j+x-1)*(2*n+1)+k+n; // 第二条边 （j,k）->(j+i,k), 每一段是 (j+x,k)->(j+x+1, k)
					s[t].square[s[t].belong++] = num; // t号火柴棒参与了num这个正方形的构建
					t = (j+i-1)*(2*n+1)+k+x; // 第三条边 (j+i,k)->(j+i, k+i), 每一段是(j+i, k+x)到(j+i, k+x+1)
					s[t].square[s[t].belong++] = num; // t号火柴棒参与了num这个正方形的构建
					t = (j+x-1)*(2*n+1)+k+i+n; // 第四条边 （j,k+i）->(j+i,k+i), 每一段是 (j+x,k+i)->(j+x+1, k+i)
					s[t].square[s[t].belong++] = num; // t号火柴棒参与了num这个正方形的构建
				}
			}
		}
	}
}

void dfs(int i, int step) // 当前决定s[i]是否移除. 为了尽快找到一组解, 显然先考虑移除, step是迄今（不包括当前步骤）已经移除了多少个正方形
{
	if (!remain) // 得到一组解了
	{
		ans = min(ans, step);
		return;
	}
	if (i==nnn||step+remain/3>=ans) // 剪枝! i越界了自然不必说. step是当前已移除的火柴棒数量. remain是剩下的正方形数量, 而移除一根火柴棒至多导致n个正方形消失, 所以至少还需要移除remain/n根火柴棒,注意, 这里本应该是remain/n而不是除以3. 但是为了过此题, 我赌了一把~ 除以3(除以2的话,会WA)
	{
		return;
	}
	if (!s[i].initexist) // 如果初始状态就是移除的
	{
		dfs(i+1, step); // 则只能继续
	}
	else
	{
		bool ov[100]; // 临时保存原数据,用于恢复现场
		int oremain = remain; // 临时保存原本的remain, 用于恢复现场
		memcpy(ov, v, sizeof(v));
		for (int j = 0; j< s[i].belong; j++)
		{
			if (v[s[i].square[j]])
			{
				v[s[i].square[j]] = false; // 此正方形消失
				remain--;
			}
		} // 做完移除s[i]这条火柴棒的操作
		dfs(i+1, step+1);
		remain = oremain;
		memcpy(v,ov,sizeof(v)); // 恢复
		dfs(i+1, step); // 不选择移除s[i]这根火柴棒
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int kase;
	scanf("%d", &kase);
	while(kase--)
	{
		scanf("%d%d", &n,&k);
		init();
		while(k)
		{
			int x;
			scanf("%d", &x);
			s[x].initexist = false; // 移除x编号的火柴棒
			for (int i = 0; i<s[x].belong; i++) // 随着x编号的火柴棒消失, 它参与构建的正方形也都消失了
			{
				if (v[s[x].square[i]])
				{
					v[s[x].square[i]] = false; // 则这个正方形消失了
					remain--;
				}
			}
			k--;
		}
		if (n==1)
		{
			k?puts("0"):puts("1");
            continue;
		}
		sort(s+1, s+nnn+1); // 按照belong降序
		dfs(1,0);
		printf("%d\n", ans);
	}
	return 0;
}

ac情况（过的极为水~ 大佬真的勿喷~ 而且估计N=5,k=0的数据没加到数据集中，不然我铁定被T掉的）

Status Accepted
Time 844ms
Memory 108kB
Length 2999
Lang C++
Submitted 2019-09-17 11:49:28
Shared
RemoteRunId 20867515

之所以上面的代码剪枝效率不高，是因为我使用的剪枝原则仅仅是一条

如果当前已经移除的火柴棒的数量+剩下至少要移掉的火柴棒数量>=ans, 则剪枝

这个剪枝策略太粗糙了~

但不管怎么样~ 我特么就是过了!!! 来打我呀~

本题显然可以使用 IDA* 或者 DLX
IDA*不消说~ 很好基于上面的代码改造，就是人为加一个界来剪枝(因为本题就是求最少移除火柴棒数量嘛~)
而DLX的难点在于如何将本问题转换为一个精确匹配或者重复匹配问题.
说过了，DLX算法的01矩阵的列是约束, 行是状态. 约束是什么呢? 就是每个正方形一定要有一条边缺失才行. 而行就是移除每根火柴棒（注意，本题移除火柴棒是1，没移除是0），所以该01矩阵的每行其实就是刻画移除了某根火柴棒的话，会造成哪些正方形被破坏. 需要保证的是, 每列至少一个1, 我们至少要选择多少行. 这不就是一个DLX的重复匹配问题了吗? 但是注意哈~ 其实DLX本质也是一个dfs(只是缩小问题速度和回溯非常迅速而已). 所以你既可以裸的等着求出一组解用该解来剪枝, 也可以DLX+IDA 来人为设定一个界来剪枝. 据网友说, 本题DLX+IDA会快的飞起~