[洛谷P4011]孤岛营救问题

发布于 2018-10-01  68 次阅读


题目

题目描述

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

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

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

输入格式

输出格式

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

输入样例

输出样例

说明

题解

基本方法

虽然它是网络流24题,但是其实根本不用网络流做。
首先我们来看看这个题目的数据范围,挺有意思的。
\(N,M,P\le10\)钥匙种类和地图大小都很小,嗯,感觉可以广搜,置于钥匙,我们就可以状态压缩一下

变量名 变量作用
\(vis_{i,j,k}\) 记录你是否揣着\(k\)这个集合的钥匙到过\((i,j)\)处
\(map_{x1,y1,x2,y2}\) 表示\((x1,y1)\)到\((x2,y2)\)是个什么情况
\(key_{i,j,k}\) 表示\((i,j)\)存放的第\(k\)把钥匙
\(num_{i,j}\) 表示在\((i,j)\)处有几把钥匙
\(tt\) 当前携带的钥匙集合

状态压缩

至于状态压缩的话,假设现在有5种钥匙,我们用1表示现在身上有,0没有。初始情况:

|0|0|0|0|0|
|-|-|-|-|-|
现在,我们来了第二把钥匙(从右往左)

|0|0|0|1|0|
|-|-|-|-|-|
这东西是不是很像二进制?
所以我们就可以用二进制来进行状压。
每次我们得到钥匙时,$$ tt|=1<<(key[i][j][k]-1) $$
每次查询是否有第i把钥匙时,只要$$ tt\&(1<<(i-1)) $$为真,我们就可以认为有这把钥匙。

代码


哇,你居然发现了这里!