[USACO23OPEN] Custodial Cleanup G 题解

FFTotoro · 2023-04-03 22:26:23 · 题解

解法

本题需要使用广度优先搜索。

先来考虑 C_i=F_i 的部分分要怎么做。不考虑所有满足 F_i=S_i 的房间（因为这些房间肯定有解），只有可以拿到其他房间所有需要的钥匙（即 C_i 或 F_i），我们才可以打开其他所有房间的房门。具体地，放钥匙的方法即为：每到一个房间，把该房间需要的钥匙放进去（因为 C_i=F_i，所以如果拿到所有的钥匙，我们最后一定可以进入所有的房间），然后离开该房间。

正解则需要一点处理技巧。我们发现最后放钥匙的过程难以确定放置的顺序（因为一个房间钥匙放下去，总是会牵扯到另外某一些房间，可能是没钥匙进不了房门），不妨换个角度想一想——如果我们把放钥匙的过程改成“拿钥匙”，即初始状态为“所有的房间都有一把颜色为 F_i 的钥匙”，是不是就可以转化为上面的问题？

但是，如果我们把状态改变成了上面的样子，那么题目条件中“持有该房间门的颜色的钥匙才能进入”的规则就得变为“持有对应颜色的钥匙才能出去”。

这样，跑两次广搜，前一次跑改变状态的，后一次跑类似部分分的那一种普通广搜。如果前一次广搜有搜到某一个房间，然而后一次没有搜到，那么肯定无解，因为钥匙放不回去了。如果两次都没搜到并且 S_i\ne F_i，也是无解的。

实现

值得注意的是，广搜过程中如果碰到因颜色权限不能进入的门时，可以建立一个二维数组 l，其中 l_i 表示门的颜色是 i 的房间有哪些，一旦拿到颜色为 i 的钥匙，就可以打开这些房门（即，将这些房间放入队列），然后清空 l_i 即可。