题解：CF2068I Pinball

· · 题解

经过读题，可以发现：

  1. 斜墙可以拆。
  2. 块状墙不能拆。
  3. 在不拆墙的情况下，球总是会来回弹。

其中，来回弹指球在一个环路上（很可能退化成在路径上往复运动）绕。 对于样例（没有回路的情况） 回路大概就是（其实不一定是四角墙，但一定全部是斜墙）

我们可以分析发现，在这次拆墙和下一次拆墙之间，求总是在来回弹。

然后我们如果认为每两个格子的边界是两个点（不同方向），就可以发现最终图会被完全剖分成若干个环。

然后考虑拆墙的影响。

拆墙显然只会影响两个环路。

这两个环路显然会都裂开成两部分，然后拼成两个新环路。

环的情况 样例情况

这也就意味着在拆 k 次墙的情况下，求最远只能到距离为 k 的环路。

我们考虑是否存在正好拆 k 次墙的情况下，让球达到距离为 k 的环。

这似乎是可以的。

我们考虑取出一条这样的路径，然后反序考虑。

考虑路径上的墙都被拆掉了，我们可以选择时机恢复，恢复了之后就不能再拆。

我们从最终情况考虑。

每次恢复墙都是将原先两个环路都拆开成两部分，一共四部分，然后拼接成两个新环路，显然我们可以选择恰当的时机，可以是球进入两个环路中的任意一个，所以 k 次操作一定可以回到起点。

所以这是一定可行的。

于是直接最短路，可以不用建出边。 其实可以 0-1 bfs。