台湾菜

ZOJ 3209 Treasure Map

twcai • acm/icpc

精确覆盖问题,看着DLX算法的伪码打的。
以格子为行,矩形为列,构造一个描述覆盖情况的矩形,用DLX算法求解。

其他可以用dancing links求解的题目还有
nuaa 1267 N皇后问题
hust 1017 Exact Cover
23849 clumsydragon 1017 Accepted 1872 kb 256 ms C++ 2253 B 2009-07-10 13:37:56
spoj 1771 Yet Another N-Queen Problem
2559174 2009-07-12 07:19:00 CD Yet Another N-Queen Problem accepted 0.36 2.6M C++
tju 3219 Radar
fzu 1686 神龙的难题
神龙的难题允许overlap的覆盖,写了3遍还是TLE,先放一放

贴下3209的代码
#include
#include
using namespace std;

#define sz 451451

int l[sz], r[sz], u[sz], d[sz], y[sz];
int s[961];

int n, m, ret;

inline void remove(const int &c) {
int i, j;
r[l[c]] = r[c];
l[r[c]] = l[c];
for(i = d[c]; i != c; i = d[i]) {
for(j = r[i]; j != i; j = r[j]) {
d[u[j]] = d[j];
u[d[j]] = u[j];
s[y[j]] --;
}
}
}

inline void resume(const int &c) {
int i, j;
for(i = u[c]; i != c; i = u[i]) {
for(j = l[i]; j != i; j = l[j]) {
d[u[j]] = j;
u[d[j]] = j;
s[y[j]] ++;
}
}
r[l[c]] = c;
l[r[c]] = c;
}

inline int dfs(int k) {
if(ret <= k)
return 0;

int i, j, c;
if(r[0] == 0) {
if(k < ret)
ret = k;
return 1;
}
int mi = 0x7FFFFFFF;
for(i = r[0]; i; i = r[i]) {
if(s[i] < mi) {
mi = s[i];
c = i;
}
}

remove(c);
for(i = d[c]; i != c; i = d[i]) {
for(j = r[i]; j != i; j = r[j]) {
remove(y[j]);
}

dfs(k + 1);

for(j = l[i]; j != i; j = l[j]) {
resume(y[j]);
}
}
resume(c);

return 0;
}

int main()
{
int t, tn, tm, t1, t2, pos;
int i, j, k;
int x1, y1, x2, y2;
scanf("%d", &t);

while(t --) {
scanf("%d %d %d", &tn, &tm, &n);
m = tn * tm;
for(i = 0; i <= m; i++) {
if(i + 1 > m)
t1 = 0;
else
t1 = i + 1;
r[i] = t1, l[t1] = i;
u[i] = i;
s[i] = 0;
}

int hd;
t2 = m + 1;

for(i = 1; i <= n; i++) {
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
hd = t2;
x2 --, y2 --;
for(j = y1; j <= y2; j++) {
pos = j * tn + x1 + 1;
for(k = x1; k <= x2; k++) {
t1 = t2;
if(j == y2 && k == x2)
t2 = hd;
else
t2 ++;
u[t1] = u[pos], d[u[t1]] = t1;
u[pos] = t1, s[pos] ++;
r[t1] = t2, l[t2] = t1;
y[t1] = pos;
pos++;
}
}
t2 = t1 + 1;
}

bool fg = 1;

for(j = 1; j <= m; j++) {
if(!s[j]) {
fg = 0;
break;
}
d[u[j]] = j;
}

if(!fg)
printf("-1\n");
else {
ret = 0x7FFFFFFF;
dfs(0);
if(ret == 0x7FFFFFFF)
printf("-1\n");
else
printf("%d\n", ret);
}
}
return 0;
}

/*
2

5 10 9
0 0 5 1
0 1 5 2
0 2 5 3
0 3 5 4
0 4 5 5
0 5 5 10
2 3 5 10
0 5 2 10
0 3 2 5

30 30 8
0 0 11 30
11 0 30 11
11 11 20 20
11 20 20 30
20 11 30 30
0 0 11 11
0 11 11 30
0 0 30 20
*/

comments powered by Disqus