Description

“挖矿小子”是一个经典的益智小游戏。玩家需要指挥矿工下地挖掘宝藏，每次矿工可以挖开其左边、右边或下方的格子，不可以挖上方的格子。矿工往下挖矿后就再也不能上来。获得所有宝藏后游戏结束。

这个游戏太简单了，在 \(3 \mathrm{D}\) 版 2048 出现之前若干年，就有人开发出了 \(3 \mathrm{D}\) 版的 “挖矿小
子”。

游戏的地图是一个 \(h \times n \times m\) 的立方体。立方体由上至下共有 \(h\) 层，编号依次为
\(1,2, \ldots, h\)，每层是一个 \(n \times m\) 的方阵。你可以假定地面层的编号为 0 。初始时所有单位立
方体 (简称单位) 均有泥土，一些单位有宝藏。挖开单位 \((i, j, k)\) (第 \(i\) 层第 \(j\) 行第 \(k\) 列，\(1 \leq i \leq h, 1 \leq j \leq n, 1 \leq k \leq m\) ) 的泥土消耗的体力为 \(a[i, j, k]\) 。当矿工在单位 \((z, x, y)\)
时，他可以不费体力地获得该单位的宝藏 （如果有的话），同时他可以挖开任一相邻单位（\((z, x-1, y),(z, x+1, y),(z, x, y-1),(z, x, y+1),(z+1, x, y)\)）的泥土，如果相邻单位的泥土已经被挖走, 则矿工可以直接到达该单位而不消耗任何体力。矿工不可以到达地图范围之外。和普通版游戏一样, 矿工不可以挖所在位置上方的单位，如果矿工挖开其下方的单位，他会掉落到下一层，并永远不能回到原来所在的层。当矿工获得所有宝藏时，游戏结束，得分为矿工消耗的总体力。

现在你正在玩这个游戏的某一关，在 \(a[i, j, k]\) 和宝藏位置已知的情况下，你需要让你的
矿工顺利地获得所有的宝藏，并使他消耗的体力最少。

Solution

这题是 WC2008 游览计划的加强版，本题中 \(h\) 不再为 1，但我们依旧可以采用同样的方法，用状压 \(\mathrm{DP}\) 来解决此题。

设 \(f_{i,j,k,s}\) 表示到了第 \(i\) 层，在第 \(j\) 行，第 \(k\) 列，宝藏状态为 \(s\)。

先枚举 \(s\) 的子集 \(ss\)，转移方程：\(f_{i,j,k,s}=\min(f_{i,j,k,ss}+f_{i,j,k,s-ss}-a_{i,j,k})\)。

然后枚举 \((j,k)\) 周围的单位，转移方程：\(f_{i,j,k,s}=\min(f_{i,x,y,s}+a_{i,j,k})\)。

注意到第 2 个转移方程有后效性，所以用 \(spfa\) 来转移。

至于层与层之间，考虑新建一个节点，表示当前层宝藏全都取完了，然后转移。

Code

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 15
#define inf 0X3f3f3f3f
using namespace std;
struct node
{
    int x,y;
};
queue<node> q;
int h,n,m,x,y,ans=0X3f3f3f3f,mp[N][N][N],cnt[N],bz[N][N][N],f[N][N][N][1<<10],fx[5]={0,0,0,1,-1},fy[5]={0,1,-1,0,0};
bool bj[N][N];
void spfa(int i,int s)
{
    while (!q.empty())
    {
        node u=q.front();q.pop();
        for (int k=1;k<=4;++k)
        {
            int x=u.x+fx[k],y=u.y+fy[k];
            if (x<1||x>n||y<1||y>m) continue;
            if (f[i][x][y][s]>f[i][u.x][u.y][s]+mp[i][x][y])
            {
                f[i][x][y][s]=f[i][u.x][u.y][s]+mp[i][x][y];
                if (!bj[x][y])
                {
                    q.push((node){x,y});
                    bj[x][y]=true;
                }
            }
        }
        bj[u.x][u.y]=false;
    }
}
int main()
{
    freopen("treasure.in","r",stdin);
    freopen("treasure.out","w",stdout);
    scanf("%d%d%d",&h,&n,&m);
    for (int i=1;i<=h;++i)
        for (int j=1;j<=n;++j)
            for (int k=1;k<=m;++k)
                scanf("%d",&mp[i][j][k]);
    for (int i=1;i<=h;++i)
    {
        scanf("%d",&cnt[i]);
        for (int j=1;j<=cnt[i];++j)
        {
            scanf("%d%d",&x,&y);
            bz[i][x][y]=j;
        }
        if (i>1) ++cnt[i];
    }
    memset(f,0x3f3f3f3f,sizeof(f));
    for (int i=1;i<=h;++i)
    {
        for (int j=1;j<=n;++j)
            for (int k=1;k<=m;++k)
            {
                if (bz[i][j][k]) f[i][j][k][1<<(bz[i][j][k]-1)]=mp[i][j][k];
                else f[i][j][k][0]=mp[i][j][k];
            }
        for (int s=0;s<(1<<cnt[i]);++s)
        {
            for (int j=1;j<=n;++j)
                for (int k=1;k<=m;++k)
                {
                    for (int ss=s;ss;--ss)
                    {
                        if ((ss|s)!=s) continue;
                        f[i][j][k][s]=min(f[i][j][k][s],f[i][j][k][ss]+f[i][j][k][s-ss]-mp[i][j][k]);
                    }
                    if (f[i][j][k][s]<inf) q.push(node{j,k}),bj[j][k]=true;
                }
            spfa(i,s);
            if (s==(1<<cnt[i])-1)
            {
                for (int j=1;j<=n;++j)
                    for (int k=1;k<=m;++k)
                    {
                        if (f[i][j][k][s]>=inf) continue;
                        if (i==h) ans=min(ans,f[i][j][k][s]);
                        else if (bz[i+1][j][k]) f[i+1][j][k][(1<<(cnt[i+1]-1))|(1<<(bz[i+1][j][k]-1))]=f[i][j][k][s]+mp[i+1][j][k];
                        else f[i+1][j][k][1<<(cnt[i+1]-1)]=f[i][j][k][s]+mp[i+1][j][k];
                    }
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}