FZU 1686 神龙的难题(重复覆盖问题舞蹈链)

本文主要是介绍FZU 1686 神龙的难题(重复覆盖问题舞蹈链)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：[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;
}