DLX反复覆盖：
须要一个A*函数剪支
Problem 1686 神龙的难题
Accept: 462 Submit: 1401 Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem Description
这是个剑与魔法的世界.英雄和魔物同在,动荡和安定并存.但总的来说,库尔特王国是个安宁的国家,人民安居乐业,魔物也比較少.可是.总有一些魔物不时会进入城市附近,干扰人民的生活.就要有一些人出来守护居民们不被魔物侵害.魔法使艾米莉就是这种一个人.她骑着她的坐骑,神龙米格拉一起消灭干扰人类生存的魔物,维护王国的安定.艾米莉希望可以在损伤最小的前提下完毕任务.每次战斗前,她都用时间停止魔法停住时间,然后米格拉他就行发出火球烧死敌人.米格拉想知道,他怎样以最快的速度消灭敌人,减轻艾米莉的负担.
Input
数据有多组,你要处理到EOF为止.每组数据第一行有两个数,n,m,(1<=n,m<=15)表示这次任务的地区范围. 然后接下来有n行,每行m个整数,如为1表示该点有怪物,为0表示该点无怪物.然后接下一行有两个整数,n1,m1 (n1<=n,m1<=m)分别表示米格拉一次能攻击的行,列数(行列不能互换),如果米格拉一单位时间能发出一个火球,全部怪物都可一击必杀.
Output
输出一行,一个整数,表示米格拉消灭全部魔物的最短时间.
Sample Input
4 41 0 0 10 1 1 00 1 1 01 0 0 12 24 4 0 0 0 00 1 1 00 1 1 00 0 0 02 2
Sample Output
41
Source
FOJ月赛-2009年2月- TimeLoop #include#include #include #include using namespace std;const int maxn=250,maxm=250;const int maxnode=maxn*maxm;const int INF=0x3f3f3f3f;int n,m;int GA[20][20];struct DLX{ int n,m,size; int U[maxnode],D[maxnode],R[maxnode],L[maxnode],Row[maxnode],Col[maxnode]; int H[maxnode],S[maxnode]; bool vis[maxm]; int ansd; void init(int _n,int _m) { ansd=INF; n=_n; m=_m; for(int i=0;i<=m;i++) { S[i]=0; U[i]=D[i]=i; L[i]=i-1; R[i]=i+1; } R[m]=0; L[0]=m; size=m; for(int i=1;i<=n;i++) { H[i]=-1; } } void Link(int r,int c) { ++S[Col[++size]=c]; Row[size]=r; D[size]=D[c]; U[D[c]]=size; U[size]=c; D[c]=size; if(H[r]<0) H[r]=L[size]=R[size]=size; else { R[size]=R[H[r]]; L[R[H[r]]]=size; L[size]=H[r]; R[H[r]]=size; } } void remove(int c) { for(int i=D[c];i!=c;i=D[i]) L[R[i]]=L[i],R[L[i]]=R[i]; } void resume(int c) { for(int i=U[c];i!=c;i=U[i]) L[R[i]]=R[L[i]]=i; } int Astart() { int ret=0; for(int i=R[0];i!=0;i=R[i]) vis[i]=true; for(int c=R[0];c!=0;c=R[c]) { if(vis[c]==true) { ret++; vis[c]=false; for(int i=D[c];i!=c;i=D[i]) for(int j=R[i];j!=i;j=R[j]) vis[Col[j]]=false; } } return ret; } void Dance(int d) { if(d+Astart()>=ansd) return ; if(R[0]==0) { ///find ans; ansd=min(ansd,d); return ; } int c=R[0]; for(int i=R[0];i!=0;i=R[i]) if(S[i]