P3707. 亲子游戏

解题思路

最短路径长度与糖果数

最短路径长度 level 很容易使用 BFS 计算得到，即计算从妈妈位置 (sx, sy) 到宝宝位置 (tx, ty) 的 BFS 搜索层数即可。本题难点在于如何计算最短路径长度 level 下能够得到最多糖果。

某一个位置 (x, y)，很可能是可以从不同方向进入多次的，如以下例子，从 -3 到 -2 的最短路径长度为 4，但有多条路径可以到达终点。

标注搜索层数。

动态规划思想

容易发现，对于 BFS 来说，只有当前层的位置都考虑过了之后（即得知到达该位置最多能拿到多少糖果之后），其下一层的位置才会被考虑。这显然是一种 dp 思想，满足 dp 的无后效性。

比如对于位置 (1,1) 而言（属于第二层），从上边或者从左边两个方向（属于第一层）均可以进入这个位置。在最短路径的限制条件下，不可能选择从右边或者从下边两个方向（属于第三层）进入这个位置。

因此，为了使得进入位置 (1,1) 获得的糖果数尽可能地多，我们会选择从上一层中获得糖果数更多的位置 (0,1) 进入这个位置。

构建 dp 数组

构建出相应的二维 dp 数组。dp[i][j] 表示进入位置 (i, j) 时能获得的最多糖果数。

第二次 BFS 过程只搜索 level 层。考虑 BFS 每一层搜索的过程中，从位置 (i, j) 进入位置 (ni, nj) 时 dp[ni][nj] 的更新，此时 dp[i][j] 的值已经从上一层搜索中确定了。构建对应的动态转移方程：

• 若 (ni, nj) 不是孩子位置时：

• 若 (ni, nj) 是孩子位置时：

以上述例子为例，最终 dp 数组的结果为：

第二次 BFS 的实现矛盾与解决方案

在第二次 BFS 过程的具体实现中，需要解决一个矛盾点：

• 每一个 (nx, ny) 只需要从其上一层的某一个 (x, y) 入队 1 次，这样才能保证不超时。
• dp[nx][ny] 的更新，必须考虑到其上一层的每一个 (x, y)，这样才能保证 dp[nx][ny] 的正确性。

其中一种解决方案是，把 dp 数组也作为 check_list 数组来使用，初始化 dp 数组中的每一个元素为 -1。dp[nx][ny] == -1 表示点 (nx, ny) 尚未被检查过，尚未入队。

复杂度分析 设地图边长为 N，格子总数为 N^2。开头找妈妈和孩子位置的双重循环是 O(N^2)。整个算法做了两次 BFS：第一次从妈妈位置出发求最短路径层数 level，check_list 保证每个格子至多入队一次，每次出队只看 4 个方向，为 O(N^2)；第二次 BFS 兼做动态规划，dp 数组同时充当检查数组（dp[nx][ny] 为 -1 时才允许入队），所以每个格子同样至多入队一次，出队后对每个邻居做的 max 动态转移是常数次操作，也为 O(N^2)。总时间复杂度 O(N^2)，瓶颈在两次对全图的层序搜索。空间上，check_list 和 dp 数组各占 O(N^2)，队列最坏时容纳一整层的格子也不超过 O(N^2)，故空间复杂度 O(N^2)。