信息学集训队作业9911报告

1、POI VI Stage 3 Problem 2仓库管理员题意分析这是一道建立在平面网格基础上的题目。不难发现：人推箱子的条件和一次推动后的情形是关键。如图一所示：人必须站在处才能将箱子往右人必须 推，而站在处则不可以将箱子往右推！站在这个位要把箱子推到相邻的某个格子中，人必须站在相应的合适位置，而不是随意站在箱子的四周。这就是说，把箱子推到指定位置，不仅仅只有箱子的位置起着作用，人的位置也起着很大的作用。置才能把箱子往右推图 一再例如图二中，处是箱子的目标位置。人站在 A 位置或B 位置对结果的影响是巨大的：A 位置有解，B 位置无解。图 二所以，分重要的。在设计算法时，除了考虑箱子位置还应

2、当考虑人的位置，这是十题目要求的是用最少的推动次数把箱子推到指定位置。解决这类问题，通常用经典的求最短路或者宽度搜索。下面，就从这方面着手，看看如何设计一个有效的算法。算法设计在题意分析中，已经知道：箱子的位置与人的位置都会对解的结果产生影响。因此，在设计算法的时候，这两者都要被考虑。不妨将它们放在一起，组成一个状态，然后求从初始状态达到目标状态最少要推多少步。初状态由初始时人的位置和箱子的位置组成，目标状态可能有很多，箱子的位置固定，人的位置可以随意。这样，可。然而当大的改进。似乎只需要用宽度搜索从初始状态开始将所有状态遍历一遍即再仔细分析就会发现：无论是空间还是时间，这个方法都需要极（一）

3、空间由于题目中N、M 的最大可能达到 100，也就是说，最多有 10000 个格子，那么状态的总数就是 1000010000！这无论是从保存的角度来看还是从遍历的效率来看，都是不可以被接受的。AB再仔细看题目，发现，任何状态都可以转化成：人的位置与箱子位置相邻的状态，否则就是无解。如图三所示：不可移动的货物等价于空闲的格子放箱子的格子箱子的目标格子人的位置管理员可以通过移动，到达和箱子邻近的格子，而这期间不会增加推动箱子的次数。图 三而图四中，无法转化成人的位置与箱子的位置相邻的状态。所以显然无解。既然所有状态可以等价转化成人的位置与箱子的位置相邻的管理员无法通过移动到达与箱子相邻的位置，也就

4、无法再推动箱子。自然就无解。状态。那么，在操作时，只需要人的位置与箱子的位置相邻的状态即可。可以重新设定状态的表示：箱子的位置以及人在箱子哪个方向的相邻格子上（上下左右）。这样一来，状态的总数就大大图 四下降，最多也不过 40000 个。空间上完全可以保存下了。经过空间上的改进，大致可以得到这样一个算法：从初始状态以宽度搜索方式遍历所有状态（遍历过的状态不被重复遍历），其中，从一个状态拓展到其他状态的方法是部分，如下：推动箱子，人动一步如果此状态人可以推动箱子（判断箱子要被推到的格子是否是空闲的），那么可以拓展出一个新的状态，如图五所示。往右推动箱子，得到新状态。图五推动箱子，人移到箱子另一边

5、推动箱子后，人从与箱子相邻的一个方向移动到其他方向相邻的格子，拓展出新的状态。如图六所示：如何判断人把箱子往右推后，能不能移动到 A 点呢？常用的方法自然就是“灌水法”，复杂度为 O(NM)。那么，总的看来，该算法的时间复杂度为 O(N2M2)，效率不太能灌水法：从开始遍历整个图，判断A 点是否被遍历到。图中表示不能被遍历到。图 六够被接受。还需要在算法的时间效率上进行改进。A（二）时间在上述的分析中，发现，判断“人能不能从箱子的一个相邻格子移动到另一个相邻格子”是造成算法效率低下的瓶颈。如果能够大幅度降低这个判断的时间复杂度，那么整个算法的复杂度也会随之降低。如图七所示，假设当前箱子在 C 处，管理员能否从A 位置移动到B 位置呢？当箱子不在 C 处时，管理员可以直接走ACB；当箱子在C 处，阻碍了管理员的上述路线，如果管理员可以走别的路线从A 到达 B，显然 A和B 是处在某一条环上的；如果不经过 C 就无法从A 到B，显然 C 是A 到 B 的关键点。图 七这样分析后，可以应用图论中的“割顶和块”1的算法来解决上述问题：事先进行预处理，求出图中的所有块；当 C 被箱子占据后，根据块的性质。如果 A、B 在一个块上，则从 A 仍然可以移动到B；如果 A 和 B 不在一个块中，则从A 不能移动到B。由于预处理求块的复杂度为 O(NM)，