HDU 3475 Street Lamp

maxc1017

　　HDU_3475
　　    由于每个灯的状态有可能控制周围八个灯的状态，这样在dp的时候就要记录至少两行灯的状态的信息，通过枚举对当前行的操作使上一行的灯全部熄灭来完成状态的转移。
　　    如果裸着做的话必然超时，因此要对dp进行优化。
　　    首先，虽然至多有2^10*2^10种不同的状态，但这些状态绝大多数是不合法的，因此我们在dp的过程中可以用一个哈希表记录下来当前拓展出的所有合法的状态，每次只取哈希表中的状态进行决策、转移，这样无论是在空间上还是时间上都优化了很多。
　　    尽管用哈希表解决了空间上的问题，也优化掉了很多无用的状态，但还是会超时，因为对于每一个状态，如果我们都枚举当前行的所有操作的话，那么每次都相当于乘一个1024的常数，但是就真的有那么多可能的操作使得上一行还未熄灭的灯全部熄灭吗？我们不妨换个角度想，先假设我们枚举了1024种操作，那么每种操作对应能改变上一行中哪些灯也就确定了，而上一行灯的这状态至多也就1024种，很可能还会因为出现重复而变得更少，换言之，对于前一行所有的可能的灯的状态，能够使其全部熄灭的所能进行的操作数一共也不过1024种，而我们却要对其中任意一种灯的状态都进行1024次枚举，显然就划不来了。所以我们先预处理出来在前一行灯是某种状态时，能够让其熄灭的所有可能的操作，并用邻接表存储，这样我们每次就不用1024次枚举了，而是能够直接尝试能使前一行灯熄灭的所有操作。
　　    那么怎么预处理呢？显然不能枚举上一行灯的状态再枚举当前行的操作看能否使其全部熄灭，这样做就又回到了当初复杂的做法了，是没意义的。我们可以枚举当前行的1024种操作，对于枚举到的每一个操作op，这时上一行能改变哪些灯就确定了，不妨设这个状态是st，那么我们就可以将op插入到以st为表头的链表中去了，这样对于任意一行我们只要枚举1024次就可以完成预处理了。当然，1024只是最坏的情况，为了说起来方便前文就都用的是1024了。



#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXN 110
#define MAXM 15
#define MAXD 10010
#define HASH 10007
#define ST 1030
#define INF 0x3f3f3f3f
int N, M, D, d[MAXN][MAXM][8], g[MAXN][MAXM], first[ST], e, next[ST], v[ST];
char b[MAXN];
struct HashMap
{
int head[HASH], size, next[MAXD], st[MAXD], ans[MAXD];
void init()
{
memset(head, -1, sizeof(head)), size = 0;   
}
void push(int _st, int _ans)
{
int i, h = _st % HASH;
for(i = head[h]; i != -1; i = next)
if(st == _st) break;
if(i == -1)
{
if(_st == -1) for(;;);
st[size] = _st, ans[size] = _ans;
next[size] = head[h], head[h] = size ++;
}
else ans = std::min(ans, _ans);
}
}hm[2];
void add(int x, int y)
{
v[e] = y;
next[e] = first[x], first[x] = e ++;
}
void prepare(int i)
{
int j, k, st;
memset(first, -1, sizeof(first)), e = 0;
for(j = 0; j <= D; j ++)
{
st = 0;
for(k = 0; k < M; k ++)
if(j & 1 << k)
{
if(d[k][5]) st ^= 1 << k - 1;
if(d[k][4]) st ^= 1 << k;
if(d[k][3]) st ^= 1 << k + 1;   
}
add(st, j);
}
}
void init()
{
int i, j, k;
scanf("%d%d", &N, &M);
memset(d, 0, sizeof(d));
memset(g, 0, sizeof(g));
gets(b);
for(i = 0; i < N; i ++)
{
gets(b);
for(j = 0; j < M; j ++)
{
g[j] = b[2 * j] == 'o';
if(j < M - 1 && b[2 * j + 1] == '-') d[j][2] = d[j + 1][6] = 1;
}
if(i < N - 1)
{
gets(b);
for(j = 0; j < M; j ++)
{
if(b[2 * j] == '|') d[j][0] = d[i + 1][j][4] = 1;
if(j < M - 1)
{
if(b[2 * j + 1] == '\\' || b[2 * j + 1] == 'X') d[j][1] = d[i + 1][j + 1][5] = 1;
if(b[2 * j + 1] == '/' || b[2 * j + 1] == 'X') d[j + 1][7] = d[i + 1][j][3] = 1;
}
}
}
}
D = (1 << M) - 1;
}
void solve()
{
int i, j, k, t, cur = 0, st, tc, td, nl, ust, cst, cnt, ans = INF;
hm[0].init();
for(i = st = 0; i < M; i ++) if(g[0]) st |= 1 << i;
hm[0].push(st, 0);
for(i = 0; i < N; i ++)
{
hm[cur ^ 1].init();
prepare(i);
for(j = nl = 0; j < M; j ++) if(g[i + 1][j]) nl |= 1 << j;
for(j = 0; j < hm[cur].size; j ++)   
{
ust = hm[cur].st[j] >> M, cst = hm[cur].st[j] & D, td = nl;
for(k = first[ust]; k != -1; k = next[k])
{
st = v[k], cnt = 0;
tc = cst ^ st, td = nl;
for(t = 0; t < M; t ++)
if(st & 1 << t)
{
++ cnt;
if(d[t][0]) td ^= 1 << t;
if(d[t][1]) td ^= 1 << t + 1;
if(d[t][2]) tc ^= 1 << t + 1;
if(d[t][6]) tc ^= 1 << t - 1;
if(d[t][7]) td ^= 1 << t - 1;   
}
hm[cur ^ 1].push(tc << M | td, hm[cur].ans[j] + cnt);
}
}
cur ^= 1;
}
for(i = 0; i < hm[cur].size; i ++)
if((hm[cur].st >> M) == 0) ans = std::min(ans, hm[cur].ans);
printf("%d\n", ans == INF ? -1 : ans);
}
int main()
{
int t, tt;
scanf("%d", &t);
for(tt = 1; tt <= t; tt ++)
{
init();
printf("Case %d: ", tt);
solve();
}
return 0;
}