神龙的难题
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Appoint description:
System Crawler (2015-04-16)
System Crawler (2015-04-16)
Description
这是个剑与魔法的世界.英雄和魔物同在,动荡和安定并存.但总的来说,库尔特王国是个安宁的国家,人民安居乐业,魔物也比较少.但是.总有一些魔物不时会进入城市附近,干扰人民的生活.就要有一些人出来守护居民们不被魔物侵害.魔法使艾米莉就是这样的一个人.她骑着她的坐骑,神龙米格拉一起消灭干扰人类生存的魔物,维护王国的安定.艾米莉希望能够在损伤最小的前提下完成任务.每次战斗前,她都用时间停止魔法停住时间,然后米格拉他就可以发出火球烧死敌人.米格拉想知道,他如何以最快的速度消灭敌人,减轻艾米莉的负担.
Input
数据有多组,你要处理到EOF为止.每组数据第一行有两个数,n,m,(1<=n,m<=15)表示这次任务的地区范围. 然后接下来有n行,每行m个整数,如为1表示该点有怪物,为0表示该点无怪物.然后接下一行有两个整数,n1,m1 (n1<=n,m1<=m)分别表示米格拉一次能攻击的行,列数(行列不能互换),假设米格拉一单位时间能发出一个火球,所有怪物都可一击必杀.
Output
输出一行,一个整数,表示米格拉消灭所有魔物的最短时间.
Sample Input
4 4 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 2 2 4 4 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 2 2
Sample Output
4 1
做DLX做得我都恶心了，每次都是TTTTTTT，这题T了两天，没话说了。
把每个有怪物的点作为列，每次攻击能达到的区域作为行，问题就转化为最少选取多少行可以使得所有列都被覆盖。重复覆盖，A*剪枝。
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
using namespace std; const int HEAD = ;
const int SIZE = * * * ;
const int INF = 0x7fffffff;
bool VIS[SIZE];
int U[SIZE],D[SIZE],L[SIZE],R[SIZE],C[SIZE],S[SIZE],LOC[SIZE];
int COUNT,ANS;
int N,M; int h(void);
void ini(void);
void dancing(int);
void remove(int);
void resume(int);
void debug(void);
int main(void)
{
int n,m; while(scanf("%d%d",&N,&M) != EOF)
{
ini();
scanf("%d%d",&n,&m); for(int i = ;i + n - <= N;i ++)
for(int j = ;j + m - <= M;j ++)
{
int first = COUNT;
for(int k = ;k < n;k ++)
for(int l = ;l < m;l ++)
{
int loc = LOC[(i + k - ) * M + j + l];
if(loc != -)
{
L[COUNT] = COUNT - ;
R[COUNT] = COUNT + ;
U[COUNT] = U[loc];
D[COUNT] = loc; D[U[loc]] = COUNT;
U[loc] = COUNT;
S[loc] ++;
C[COUNT] = loc;
COUNT ++;
}
}
if(first != COUNT)
{
L[first] = COUNT - ;
R[COUNT - ] = first;
}
}
dancing();
printf("%d\n",ANS);
} return ;
} void ini(void)
{
ANS = INF;
COUNT = ;
int box; for(int i = ;i <= N;i ++)
for(int j = ;j <= M;j ++)
{
scanf("%d",&box);
if(box)
{
L[COUNT] = COUNT - ;
R[COUNT] = COUNT + ;
U[COUNT] = D[COUNT] = COUNT;
C[COUNT] = COUNT;
S[COUNT] = ;
LOC[(i - ) * M + j] = COUNT;
COUNT ++;
}
else
LOC[(i - ) * M + j] = -;
}
if(COUNT != )
{
R[COUNT - ] = HEAD;
L[HEAD] = COUNT - ;
R[HEAD] = ;
}
else
R[HEAD] = L[HEAD] = HEAD;
} void dancing(int k)
{
if(R[HEAD] == HEAD)
{
ANS = ANS < k ? ANS : k;
return ;
}
if(k + h() >= ANS)
return ; int c = R[HEAD];
for(int i = L[HEAD];i != HEAD;i = L[i])
if(S[i] < S[c])
c = i; for(int i = D[c];i != c;i = D[i])
{
remove(i);
for(int j = R[i];j != i;j = R[j])
remove(j);
dancing(k + );
for(int j = L[i];j != i;j = L[j])
resume(j);
resume(i);
} return ;
} 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]] = i;
R[L[i]] = i;
}
} int h(void)
{
for(int i = R[HEAD];i;i = R[i])
VIS[i] = false; int sum = ;
for(int i = R[HEAD];i != HEAD;i = R[i])
if(!VIS[i])
{
sum ++;
VIS[i] = true;
for(int j = D[i];j != i;j = D[j])
for(int k = R[j];k != j;k = R[k])
VIS[C[k]] = true;
} return sum;
}