[Solution][Plug Dynamic Programming]POJ3133 Manhattan Wiring

【题目】

戳这里

【启示】

Hash表的链式存储与清空。

轮廓线的存储方式。

【思路】

插头DP(什么基于连通性的状态压缩动态规划).

波折了两天终于把插头DP入门了。。。感谢LZHH神犇。

轮廓线:分隔已决策格子和未决策格子的折线。

插头:连接相邻两个格子的部分连通路径。

状态转移:从上到下枚举每一行,对于每一行从左到右枚举每一列,枚举前一格子的所有轮廓线状态,转移当前格子的状态。

对于每一行的第一个格子,由于使用滚动数组,需要对上一行最后一个格子的状态进行变化。

推荐CDQ的论文,不过理解和写代码确实有距离。。。

【代码】

/*
    Task    : POJ3133
    Project : PlugDP && Hash
*/
#include<cstdio>
#include<cstring>
inline int _min(int a , int b)
{
    return a < b ? a : b;
}
const int Mod = 13557;
const int MaxSize = 60000;
const int INF = 1 << 30;
struct HashSet
{
    int status[MaxSize] , val[MaxSize] , ind , head[Mod] , next[MaxSize];
    void clear()
    {
        memset(head , 0 , sizeof(head));
        ind = 0;
    }
    void update(int state , int ans)
    {
        int ins = state % Mod;
        for(int i = head[ins] ; i ; i = next[i])
        {
            if (state == status[i])
            {
                val[i] = _min(val[i] , ans);
                return;
            }
        }
        next[++ind] = head[ins];
        head[ins] = ind;
        status[ind] = state;
        val[ind] = ans;
    }
}f[2];
int map[15][15];
int main()
{
    int n , m;
    register int i , j , k;
    while(scanf("%d%d" , &n , &m) == 2 && n && m)
    {
        for(i = 1 ; i <= n ; ++i)
        for(j = 1 ; j <= m ; ++j)
            scanf("%d" , &map[i][j]);
        for(i = 0 ; i <= n + 1 ; ++i)
            map[i][0] = map[i][m + 1] = 1;
        for(j = 0 ; j <= m + 1 ; ++j)
            map[0][j] = map[n + 1][j] = 1;
        int cur = 1 , last = 0;
        f[cur].clear();
        f[cur].update(0 , 0);
        for(i = 1 ; i <= n ; ++i)
        {
            for(j = 1 ; j <= m ; ++j)
            {
                cur ^= 1 , last ^= 1;
                f[cur].clear();
                for(k = 1 ; k <= f[last].ind ; ++k)
                {
                    int S = f[last].status[k];
                    int d = f[last].val[k];
                    if (j == 1)
                        S <<= 2;
                    int ins0 = 2 * j - 2;
                    int ins1 = 2 * j;
                    int st1  = (S >> ins0) & 3;
                    int st2  = (S >> ins1) & 3;
                    S = S ^ (st1 << ins0) ^ (st2 << ins1);
                    if (st1 == 0 && st2 == 0)
                    {
                        if (!map[i][j])
                        {
                            f[cur].update(S , d);
                            if (map[i][j + 1] != 1 && map[i + 1][j] != 1)
                            {
                                f[cur].update(S | (10 << ins0) , d + 1);
                                f[cur].update(S | (15 << ins0) , d + 1);
                            }
                        }
                        else if (map[i][j] == 1)
                            f[cur].update(S , d);
                        else
                        {
                            if (map[i][j + 1] != 1)
                                f[cur].update(S | (map[i][j] << ins1) , d + 1);
                            if (map[i + 1][j] != 1)
                                f[cur].update(S | (map[i][j] << ins0) , d + 1);
                        }
                    }
                    else if ((st1 == 0 && st2) || (st1 && st2 == 0))
                    {
                        if (!map[i][j])
                        {
                            st1 += st2;
                            if (map[i][j + 1] != 1)
                                f[cur].update(S | (st1 << ins1) , d + 1);
                            if (map[i + 1][j] != 1)
                                f[cur].update(S | (st1 << ins0) , d + 1);
                        }
                        else if (map[i][j] != 1 && st1 + st2 == map[i][j])
                            f[cur].update(S , d + 1);
                    }
                    else if (st1 == st2 && map[i][j] == 0)
                        f[cur].update(S , d + 1);
                }
            }
        }
        int ans = INF;
        for(i = 1 ; i <= f[cur].ind ; ++i)
            if (!f[cur].status[i] && f[cur].val[i] - 2 > 0)
                ans = _min(ans , f[cur].val[i] - 2);
        printf("%d\n" , ans == INF ? 0 : ans);
    }
    return 0;
}
comments powered by Disqus