题目链接：[kuangbin带你飞]专题三 Dancing Links D - 神龙的难题
题意
Description
这是个剑与魔法的世界.英雄和魔物同在,动荡和安定并存.但总的来说,库尔特王国是个安宁的国家,人民安居乐业,魔物也比较少.但是.总有一些魔物不时会进入城市附近,干扰人民的生活.就要有一些人出来守护居民们不被魔物侵害.魔法使艾米莉就是这样的一个人.她骑着她的坐骑,神龙米格拉一起消灭干扰人类生存的魔物,维护王国的安定.艾米莉希望能够在损伤最小的前提下完成任务.每次战斗前,她都用时间停止魔法停住时间,然后米格拉他就可以发出火球烧死敌人.米格拉想知道,他如何以最快的速度消灭敌人,减轻艾米莉的负担.
Input
数据有多组,你要处理到EOF为止.每组数据第一行有两个数,n,m,(1<=n,m<=15)表示这次任务的地区范围. 然后接下来有n行,每行m个整数,如为1表示该点有怪物,为0表示该点无怪物.然后接下一行有两个整数,n1,m1 (n1<=n,m1<=m)分别表示米格拉一次能攻击的行,列数(行列不能互换),假设米格拉一单位时间能发出一个火球,所有怪物都可一击必杀.
Output
输出一行,一个整数,表示米格拉消灭所有魔物的最短时间.
思路
精确覆盖是每次选取一行后，就要对这行的所有列诛九族。而本题是重复覆盖，所以删除时，只删除相关的列即可，不诛连。
本题需要进行剪枝，剪枝函数f()代码中已说明。
ps：a的第一道重复覆盖问题，因为数据范围被T了那么多次，欲哭无泪啊，把代码扫了一遍又一遍，就是想不到竟然是数据范围的原因。细心是王道啊。。。
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;
const int N = 16*16;
const int MAX = N*N;
int G[N][N];//储存地图
int P[MAX];//储存点编号
int U[MAX], D[MAX], L[MAX], R[MAX];//数组模拟链表指向(上下左右)
int C[MAX], M[MAX];//节点所在列与行
int S[N];//储存每列的元素数量
int H[N];//行头指针
int ans;
void init(int n, int m)
{
for(int i=0; i<=m; i++)
{
L[i+1] = i;
R[i] = i+1;
U[i] = D[i] = i;
S[i] = 0;
}
for(int i=1; i<=n; i++)
H[i] = -1;
L[0] = m;
R[m] = 0;
}
void link(int row, int col, int id)//将节点加入链表
{
C[id] = col; M[id] = row;//记录行列
U[id] = U[col]; D[U[col]] = id;//上下连接
D[id] = col; U[col] = id;
if(H[row] == -1)//左右连接(使用表头方便头插)
H[row] = L[id] = R[id] = id;
else
{
L[id] = L[H[row]]; R[L[H[row]]] = id;
L[H[row]] = id; R[id] = H[row];
}
S[col]++;
}
void remove(int col)//因为是重复覆盖，所以一次循环，只删除该列，不删除相关的
{
for(int i=D[col]; i!=col; i=D[i])
{
L[R[i]] = L[i];
R[L[i]] = R[i];
}
}
void resume(int col)
{
for(int i=U[col]; i!=col; i=U[i])
{
L[R[i]] = i;
R[L[i]] = i;
}
}
bool v[MAX];
int f()//剪枝函数
{
int num = 0;
for(int i=R[0]; i!=0; i=R[i])//0代表未消灭
v[i] = 0;
for(int i=R[0]; i!=0; i=R[i])
{
if(!v[i])
{
v[i] = 1;
num++;
//(假设攻击范围最大化)能够杀掉它的所有攻击的全部范围进行消灭，类似以它为圆心画圆一样
for(int j=U[i]; j!=i; j=U[j])
for(int k=R[j]; k!=j; k=R[k])
v[C[k]] = 1;
}
}
return num;
}
void dance(int k)
{
if(k+f() >= ans)
return;
if(!R[0])
{
ans = min(ans, k);
return;
}
int col = R[0];
for(int i=R[0]; i!=0; i=R[i])
if(S[i] < S[col])
col = i;
for(int i=D[col]; i!=col; i=D[i])
{
remove(i);
for(int j=R[i]; j!=i; j=R[j])
remove(j);
dance(k+1);
for(int j=L[i]; j!=i; j=L[j])
resume(j);
resume(i);
}
}
int main()
{
int n, m;
while(~scanf("%d%d", &n, &m))
{
int num = 0;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
{
scanf("%d", &G[i][j]);
if(G[i][j])
P[j+(i-1)*m] = ++num;
}
int r, c;
scanf("%d%d", &r, &c);
init((n-r+1)*(m-c+1), num);
int id = num+1;
for(int i=1; i<=n-r+1; i++)
{
for(int j=1; j<=m-c+1; j++)
for(int x=i; x<=i+r-1; x++)
for(int y=j; y<=j+c-1; y++)
{
if(G[x][y])
link(j+(i-1)*(m-c+1), P[y+(x-1)*m], id++);
}
}
ans = 0x3f3f3f3f;
dance(0);
printf("%d\n", ans);
}
return 0;
}