Gravatar
op_组撒头屯
积分:3036
提交:338 / 677

Pro240  [POI 1999] 仓库管理员(Store-Keeper)

首先不难想到BFS。

以及,箱子能被推动到目标方向当且仅当:①目标方向是空地;②目标方向关于箱子的对面是空地,且人能到达。


如果允许人在空地上任意传送,本题将会简单很多。令 $f_{i,j}$ 表示箱子到达 $(i,j)$ 时的最小次数,每次转移只需判断目标方向的对面是否是空地即可。

但有了沉重货物的限制,会导致人并不一定能到达箱子旁的空地(即使初始时他可以到达)。

不过不难发现,当人推动一次箱子时,他将会“取代”箱子原本的位置。也就是说,判断人是否能到达空地,实际上是判断箱子上次的位置是否能到达那里。而方向只有四个,令 $f_{i,j,0/1/2/3}$ 表示箱子到达 $(i,j)$ ,且上次它在现在的 上/下/左/右 时的最小次数。每次转移时,从上次的位置出发进行搜索,判断是否能到达目标方向对面的空地即可。

时间复杂度大常数$O(n^4)$,无法通过。


上述算法的瓶颈在于,每次转移时都要进行一次搜索,包含了大量的重复计算。我们希望通过一些预处理优化这一过程。

实际上已经很明显了。我们把每个空地抽象成点,向四周的空地连边。箱子放于 $(x,y)$ 时人无法从 $(a,b)$ 到达 $(c,d)$ ,实际上就是说 $(x,y)$ 是原图的一个割点,将 $(a,b)$ 所在连通块与 $(c,d)$ 所在连通块分离。相反,若 $(a,b)$ 与 $(c,d)$ 在同一连通块中,人肯定能相互到达。这样,通过预处理原图的相关$dcc$信息,我们可以做到$O(1)$的转移。

关于 $f$ 的初始化,需要从人的出发点单独搜一次,记录初始时人能到达的箱子旁的空地。

码量稍大,不过每一部分相对简单。


2022-11-20 21:14:10    
我有话要说
暂无人分享评论!