自动搬运

查看原文

来自洛谷，原作者为

	Lynkcat Reset.

搬运于2025-08-24 22:30:12，当前版本为作者最后更新于2021-03-28 11:47:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们考虑普通的暴力怎么做。

首先我们可以暴搜，用一个形如 $(x,y,a,b)$ 的状态，表示第一个人在 $(x,y)$ ，第二个人在 $(a,b)$ 的位置上。然后枚举上下左右四个方向暴力走，直到碰到障碍为止。

接下来考虑优化暴搜：

$1:$ 预处理出每个位置上下左右的障碍位置，这样在搜索的时候可以 $O(1)$ 跳。

$2:$ 考虑每个 $(x,y,a,b)$ 的状态互不影响，所以我们可以记忆化一下。

$3:$ 再考虑如何解决上面这个状态记忆化所需要的空间过大的问题，我们可以发现每次重力方向钦定完后，球必定是在一个障碍物的相邻格子上。所以我们先抠出所有障碍物，然后设 $(x,y,1/2/3/4)$ 表示第一个人在第 $x$ 个障碍物的上下左右，第二个人在第 $y$ 个障碍物的上下左右，减少了空间的需求量。

最后，容易发现最多只有 $4(n-1)+m$ 个障碍物，因此障碍物附近的格子最多只有 $[4n+4m]\times 4$ 个，那么总状态数只有 $16[4n+4m]^2$ 个，最多 $25000000$ 。

但是如果直接记忆化搜索会遇到一个问题，如何确定转移方向？

这个问题就非常难搞了，至少需要给源代码乘上 4 倍的常数，显然不够优。

于是我们考虑把记忆化搜索换掉，正难则反，我们考虑对于原来的状态转移图变成它的反图，然后你会发现这就是一个多源点的最短路问题，求每个点到最近的那个源点的最短路，那么这个东西就可以用 bfs 来预处理，处理过程中忽略返祖边即可。