首页 > 数据结构 > Hash表 > HDU 3475-Street Lamp-动态规划-[解题报告]HOJ
2014
04-04

HDU 3475-Street Lamp-动态规划-[解题报告]HOJ

Street Lamp

问题描述 :

There are N parallel streets, each with M street lamps, every day when it’s about to dawn, you’ll have to turn all of them off, the problem is, the lamps are wired in a strange way and turning off one lamp could affect others lamps’ on-off states! Some of the lamps of the same street are wired but some are not, so turning on or off may make the lamp direct connecting to it change state (from on to off and vice versa).

Given a state of the wirings and of the street lamps, find the minimum number of switch turn all the lamps off!

输入:

The first line is T (T <= 50), the number of test cases.
For each case, the first line containing 2 integers: N, M (0 < N <= 100 and 0 < M <= 10). Then 2N – 1 lines followed, describing the lamps and the wires between them. Each line is a street with m lamps, ‘o’ represent a lit lamp while ‘*’ represent a lamp that already be turned off, ‘|’ and ‘-’ represent a wire that connecting two neighboring lamps. And the ‘\’ ,’/’ indicates a wire sideling connecting. And ‘X’ indicates two wires sideling connecting. For more details, please read the hint for test case.

输出:

The first line is T (T <= 50), the number of test cases.
For each case, the first line containing 2 integers: N, M (0 < N <= 100 and 0 < M <= 10). Then 2N – 1 lines followed, describing the lamps and the wires between them. Each line is a street with m lamps, ‘o’ represent a lit lamp while ‘*’ represent a lamp that already be turned off, ‘|’ and ‘-’ represent a wire that connecting two neighboring lamps. And the ‘\’ ,’/’ indicates a wire sideling connecting. And ‘X’ indicates two wires sideling connecting. For more details, please read the hint for test case.

样例输入:

3
2 2
*-o
   
o-*
2 2
*-o
 \ 
o-*
2 3
o o o
 X X 
o o o

样例输出:

Case 1: -1
Case 2: 2
Case 3: 2
Hint
In the second test case, you can switch the light (0, 0) and (1, 1) to turn all the lights off. In the third test case, you can switch the light (0, 1) and (1, 1) to turn all the lights off.

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[i])
            if(st[i] == _st) break;
        if(i == -1)
        {
            if(_st == -1) for(;;);
            st[size] = _st, ans[size] = _ans;
            next[size] = head[h], head[h] = size ++;
        }
        else ans[i] = std::min(ans[i], _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[i][k][5]) st ^= 1 << k - 1;
                if(d[i][k][4]) st ^= 1 << k;
                if(d[i][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[i][j] = b[2 * j] == 'o';
            if(j < M - 1 && b[2 * j + 1] == '-') d[i][j][2] = d[i][j + 1][6] = 1;
        }
        if(i < N - 1)
        {
            gets(b);
            for(j = 0; j < M; j ++)
            {
                if(b[2 * j] == '|') d[i][j][0] = d[i + 1][j][4] = 1;
                if(j < M - 1)
                {
                    if(b[2 * j + 1] == '\\' || b[2 * j + 1] == 'X') d[i][j][1] = d[i + 1][j + 1][5] = 1;
                    if(b[2 * j + 1] == '/' || b[2 * j + 1] == 'X') d[i][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][i]) 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[i][t][0]) td ^= 1 << t;
                        if(d[i][t][1]) td ^= 1 << t + 1;
                        if(d[i][t][2]) tc ^= 1 << t + 1;
                        if(d[i][t][6]) tc ^= 1 << t - 1;
                        if(d[i][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[i] >> M) == 0) ans = std::min(ans, hm[cur].ans[i]);
    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;
}

 

 

参考:http://www.cnblogs.com/staginner/archive/2012/09/06/2673339.html


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。