题意

题目描述

\(1944\)年，特种兵麦克接到国防部的命令，要求立即赶赴太平洋上的一个孤岛，营救被敌军俘虏的大兵瑞恩。瑞恩被关押在一个迷宫里，迷宫地形复杂，但幸好麦克得到了迷宫的地形图。迷宫的外形是一个长方形，其南北方向被划分为\(N\)行，东西方向被划分为\(M\)列，于是整个迷宫被划分为\(N \times M\)个单元。每一个单元的位置可用一个有序数对(单元的行号，单元的列号)来表示。南北或东西方向相邻的\(2\)个单元之间可能互通，也可能有一扇锁着的门，或者是一堵不可逾越的墙。迷宫中有一些单元存放着钥匙，并且所有的门被分成\(P\)类，打开同一类的门的钥匙相同，不同类门的钥匙不同。

大兵瑞恩被关押在迷宫的东南角，即\((N,M)\)单元里，并已经昏迷。迷宫只有一个入口，在西北角。也就是说，麦克可以直接进入\((1,1)\)单元。另外，麦克从一个单元移动到另一个相邻单元的时间为\(1\)，拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。

试设计一个算法，帮助麦克以最快的方式到达瑞恩所在单元，营救大兵瑞恩。

输入输出格式

输入格式：

第\(1\)行有\(3\)个整数，分别表示\(N,M,P\)的值。

第\(2\)行是\(1\)个整数\(K\)，表示迷宫中门和墙的总数。

第\(I+2\)行\((1 \leq I \leq K)\)，有\(5\)个整数，依次为\(X_{i1},Y_{i1},X_{i2},Y_{i2},G_i\)：

当\(G_i \geq 1\)时，表示\((X_{i1},Y_{i1})\)单元与\((X_{i2},Y_{i2})\)单元之间有一扇第\(G_i\)类的门
当\(G_i=0\)时，表示\((X_{i1},Y_{i1})\)单元与\((X_{i2},Y_{i2})\)单元之间有一堵不可逾越的墙（其中，\(|X_{i1}-X_{i2}|+|Y_{i1}-Y_{i2}|=1\)，\(0 \leq G_i \leq P\)）。

第\(K+3\)行是一个整数\(S\)，表示迷宫中存放的钥匙总数。

第\(K+3+J\)行\((1 \leq J \leq S)\)，有\(3\)个整数，依次为\(X_{i1},Y_{i1},Q_i\)：表示第\(J\)把钥匙存放在\((X_{i1},Y_{i1})\)单元里，并且第\(J\)把钥匙是用来开启第\(Q_i\)类门的。（其中\(1 \leq Q_i \leq P\)）。

输入数据中同一行各相邻整数之间用一个空格分隔。

输出格式：

将麦克营救到大兵瑞恩的最短时间的值输出。如果问题无解，则输出\(-1\)。

输入输出样例

输入样例：

输出样例：

说明

\(|X_{i1}-X_{i2}|+|Y_{i1}-Y_{i2}|=1,0 \leq G_i \leq P\)

\(1 \leq Q_i \leq P\)

\(N,M,P \leq 10, K<150,S \leq 14\)

思路

这是一道很不错的题，可以用多种方式\(AC\)：\(A^*\)、最短路、网络流...在这里我选择的是状态压缩+最短路。

定义\(dis[i][j]\)表示在\(i\)号结点时拥有的钥匙状态为\(j\)的最短路径长度。其中，\(j\)的二进制表示下第\(k\)位表示是否拥有钥匙\(k\)。建图时，互相能连通的两点之间距离都为一，走到有钥匙的点时一定拿钥匙，稳妥地处理输入信息，就能\(AC\)了，码量也不大。

AC代码

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

const int INF=0x3f3f3f3f;

int n,m,p,k,ans=INF,dis[105][1<<15],G[105][105],gate[105][105],key[105];

int cnt,top[105],to[1005],len[1005],ned[1005],nex[1005];

bool vis[105][1<<15];

int a[2]={+1,+0};

int b[2]={+0,+1};

int read()

{

    int re=0;

    char ch=getchar();

    while(!isdigit(ch)) ch=getchar();

    while(isdigit(ch)) re=(re<<3)+(re<<1)+ch-'0',ch=getchar();

    return re;

}

inline int f(int x,int y){return (x-1)*m+y;}

inline void add_edge(int x,int y,int z,int w)

{

    to[++cnt]=y,len[cnt]=z,ned[cnt]=w,nex[cnt]=top[x],top[x]=cnt;

    to[++cnt]=x,len[cnt]=z,ned[cnt]=w,nex[cnt]=top[y],top[y]=cnt;

}

void SPFA()

{

    memset(dis,0x3f,sizeof dis);

    queue<PII>Q;

    dis[1][key[1]]=0;

    Q.push(make_pair(1,key[1]));

    while(!Q.empty())

    {

        int now=Q.front().first,con=Q.front().second;Q.pop();

        vis[now][con]=false;

        for(int i=top[now];i;i=nex[i])

            if((ned[i]&con)==ned[i])

                if(dis[to[i]][con|key[to[i]]]>dis[now][con]+len[i])

                {

                    dis[to[i]][con|key[to[i]]]=dis[now][con]+len[i];

                    if(!vis[to[i]][con|key[to[i]]])

                    {

                        vis[to[i]][con|key[to[i]]]=true;

                        Q.push(make_pair(to[i],con|key[to[i]]));

                    }

                }

    }

}

int main()

{

    n=read(),m=read(),p=read(),k=read();

    while(k--)

    {

        int x=read(),y=read(),xx=read(),yy=read(),g=read();

        if(!g) G[f(x,y)][f(xx,yy)]=G[f(xx,yy)][f(x,y)]=INF;

        else gate[f(x,y)][f(xx,yy)]=gate[f(xx,yy)][f(x,y)]=(1<<(g-1));

    }

    for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++)

            for(int w=0;w<2;w++)

            {

                int x=i+a[w],y=j+b[w];

                if(x<=0||x>n||y<=0||y>m) continue;

                add_edge(f(i,j),f(x,y),G[f(i,j)][f(x,y)]==INF?INF:1,gate[f(i,j)][f(x,y)]);

            }

    k=read();

    while(k--)

    {

        int x=read(),y=read(),z=read();

        key[f(x,y)]|=(1<<(z-1));

    }

    SPFA();

    for(int i=0;i<(1<<p);i++) ans=min(ans,dis[f(n,m)][i]);

    printf("%d",ans==INF?-1:ans);

    return 0;

}

i1

Luogu P4011 孤岛营救问题(状态压缩+最短路)

题意