题解 P7473 [NOI Online 2021 入门组] 重力球

· · 题解

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

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

接下来考虑优化暴搜：

$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 来预处理，处理过程中忽略返祖边即可。