芙卡米的详细揭秘系列 III。 $\to$ 上期回顾 $\gets$

贪吃蛇竟然引出惊天漏洞！

大家好，我是小蝙蝠卡密，相信大家都玩过贪吃蛇吧，今天我们来详细揭秘的就是一道叫做“****贪吃蛇”（由于侵犯版权而删除）的题目。

中午芙卡米一起床，就看到绿水青山（@xiaolilsq）在做此神仙题——居然是一道模拟题！不过芙卡米很快发现了数据范围中的不对劲之处：

且图中的蛇不会引起混淆（对于任意蛇头，最多只有一块蛇身于其相连）

输入保证图中的蛇均可以判断身体与头的对应关系

点开题解，绿水青山发现，题解都是直接 bfs 找到的蛇身，她不禁有疑问：难道不会出现环的情况？或者两条蛇身联通的情况？ 芙卡米表示很有兴趣，开始手动构造数据，于是她构造了一组这样的数据：

3 9 5
...#.##..
.@#####@.
...##....
WASSD
DSAAW

不难发现，这组数据有两条蛇，一条长度为 $4$；另一条为 $8$。并且也满足题目的要求，两条蛇都只有唯一一种形态。“对于任意蛇头，最多只有一块蛇身于其相连”这个条件也满足。

这组样例应该按如下模拟：

0 sec
...#.##..
.@#####@.
...##....

1 sec
.@...##..
.#######@
....#....

2 sec
@#...##..
.##.#####
........@

3 sec
##...##..
@#...####
.......@#

4 sec
##...##..
#.....###
@.....@##

5 sec
#....&&..
#.....&&&
#@....&&&

最后蛇 $2$ 应当被撞死，但芙卡米测试的前两篇题解都认为没有撞死 QAQ。

所以说直接爆搜蛇身是错误的，没有任何证据表明图中的 # 会形成彼此分离的链状结构。

可以观察如下数据，发现输入即便如此混乱，看似蛇身相互缠绕，但实际上还是有唯一对应的方法。

...................
........#..........
...@######.........
.......#.##@.......
.....###...........
.#####..@...####...
.....####.###...##.
.....#....#.##..##.
..........########@
...................

本题正解

应该采用拓扑排序。

我们对于每一条蛇都看作一个链状结构，对于每一个非蛇头结点都有且仅有一个直接祖先（前驱），且一个结点只能作为最多一个结点的直接祖先。初始我们可以确定所有叶子结点的前驱，接着我们就按照拓扑排序的方法找每一个结点的前驱即可。一个实现上的细节是：因为一个结点只能作为最多一个结点的直接祖先，所以当一个结点被定为另一个结点的直接祖先时，要把与它相邻的结点度数 $-1$。

后记

感谢 @xiaolilsq ,@Daniel_yuan对本次揭秘活动的大力支持！

以及希望加入这组 hack 数据 QWQ。

这篇讨论发了三次，这告诉我们交稿给编辑审核是非常有必要的