题解：P14141 「SFMOI Round II」Strange Mortar Game（Part1）

szh_AK_all · 2025-10-05 10:07:42 · 题解

妙妙题。

我们需要阻止敌人走到 (n,m)，那么考虑怎么挡才能让他走不到 (n,m)。首先有一个很简单的想法，就是直接把某一时刻的路全封死。并且可以发现，敌人在 x 时刻能走到的点是满足 i+j-2=x 的点 (i,j) 构成的点集，而这个点集刻画在图上就是一条斜线。所以我们如果要把某一时刻的路全封死，那就相当于要把这一时刻对应的斜线封死。如图：

但是我们拥有的不是斜线，而是若干个矩形。我们发现，如果我们要在第 i 时刻使用矩形 j，那么矩形 j 只有对应的 i 时刻的那一条斜线有用。这个好办，我们把每个矩形拆成若干条斜线，这样我们就得到了很多条用来阻挡的斜线。

然而这些斜线也不一定可以完整的封死某一时刻的路，我们考虑非完整的斜线能有什么影响，如图：

如果我们选择用红线遮挡，那么敌人若想走到绿线对应的时刻，他能走到的最靠左下角的点就是 A 点，而 A 点右上角的点也都能走到。那么如果我们选择再用一条包含 A 点及 A 点右上角的点的斜线来阻挡，敌人也无法到达 n,m。如图：

当然这条绿线也可以往左下角延长。

如果这条绿线仍然没有把路堵死，那么可以用一样的思路考虑。我们把使用的斜线看成一条路径。当我们使用一条斜线时，我们走到斜线的顶端，然后可以选择一直往下走，在某一时刻再使用另一条斜线，然后走到它的顶端，以此类推。因为斜线延长一点对答案没有影响，所以我们也可以往左走。当我们走到右上角的点时，就代表敌人无法到达 (n,m) 了。

这便转化成了一个最短路的问题，记录从左上角走到右上角最短路包含的路径、使用斜线的时刻即可。