NFLSPC #2 Pekopeko 题解

2019-11-28 23:18:52 By fizzydavid

算法1

考虑爆搜,直接枚举每一步兔子的走法和放障碍的位置。对于一种局面,判断能否围住兔子需要对于兔子所有的走法都存在至少一种对策可以将其围住。也就是说,爆搜时,若轮到兔子行动,判断可以围住兔子需要对于兔子的每一种决策都围住兔子,若轮到放障碍的人行动,判断可以围住兔子只需要某一个位置的障碍能将兔子围住就行了。若兔子走到最外圈即无法围住,若兔子无法移动则可以围住。

对于爆搜算法,不同的实现方法可以得到不同的分数。一个好的实现了下述优化的程序应该可以通过前$60$分。

以下是一些优化方法:

优化1

记忆化搜索。即遇到重复的局面不重复计算。注意这对于多组测试数据的题目有很好的效果。

优化2

兔子不会走向它走过的格子。否则,它从某个局面(第一次走到那个格子的局面)走到了比它更劣的局面(走重复的格子的局面),这一定是不优的。

优化3

当兔子紧贴最外圈时,若最外圈中相邻的格子中没有障碍,那么放障碍的人一定要放一个障碍在那里。

优化4

除了优化3中的情况,放障碍的人一定不会将障碍放在最外圈。因为这样不如将障碍往棋盘内的方向移一格。

优化5

关于结束条件判断的优化:若兔子不存在一条路径可以走到边界,就宣布兔子被围住。

优化6

考虑改变搜索的顺序。兔子的策略可以优先选择离边界最近的方向走。

优化7

考虑改变搜索的顺序。放障碍的策略可以优先选择$(2,2), (n-1, 2), (2, m-1), (n-1, m-1)$这些角上的格子,还有与兔子相邻的格子。

优化8

关于结束条件判断的优化:对于每一个格子,我们可以给它分配一个格挡的方向,当兔子进入时就令它下个回合无法走向那个方向。这里我们并不设置障碍物。注意这相当于削弱了放障碍的人,而削弱放障碍的人并不影响我们宣布兔子被围住。我们考虑这种规则下哪些格子是兔子可以逃脱的。首先边界上的格子是可以逃脱的。若一个格子相邻至少有两个可以逃脱的格子,那么它也是可以逃脱的。我们可以用bfs实现这个过程。

优化9

对于空棋盘,若兔子一开始就无法逃脱,那么兔子以后永远不会进入这个格子。

算法2

优化9是解决这个问题的关键。我们观察$10 \times 10$的空棋盘,哪些格子可以在一开始被围住:

1111111111
1111111111
1111001111
1110000111
1100000011
1100000011
1110000111
1111001111
1111111111
1111111111

注意只有靠近边界的格子兔子才能成功逃脱。此时可以对兔子的策略将格子的类型分类讨论,但是作者尚不清楚实现细节是否繁琐,所以这里暂不讨论。这里有一个简单的通过此题的方法,不过前提是你需要有一个能计算$9 \times 9$规模的程序。

我们发现对于$n>9$的情况,除去边界外,边上只剩下宽度为1的通道。我们考虑将这个通道的长度缩到$1$。假设我们缩左边的通道(用|表示):

11111
11111
11110
11100
||000
||000
||000
||000
||000
11100
11110
11111
11111

缩完以后应该长这样(用AB表示通道缩成的两个格子):

11111
11111
11110
11100
BA000
11100
11110
11111
11111

我们发现兔子经过通道时一定只有一种决策可以进行(走向没走过的那个方向),若通道格子旁边的边界格子中没有障碍,那么放障碍的人也一定需要放一个障碍。

若通道中有障碍物,那么这个通道将无法通过,可以将其等价地表示为A=X

若通道中没有障碍物,则考虑通道边界上的障碍物个数,若有一个障碍物可以将其等价地表示为A=., B=X(这是为了方便计算与边界障碍物相邻的格子作为起点时的答案),若有大于一个障碍物可以将其等价地表示为A=X

除了与边界障碍物相邻的格子作为起点的情况,以通道中其他格子作为起点的答案可以由通道两端的答案计算出来。

这样对于任意规模的$n$,都可以将其转化为$n \le 9$的情况。某种意义下,除去读入、转化、输出的时间复杂度是$O(1)$的。


Bonus

也许你会奇怪为什么这题不是$n \times m$的棋盘,这是因为长方形棋盘有非常鬼畜的情况。可以考虑$5 \times 100$、$4 \times 100$的棋盘。这里不代表不能做这些情况,只是需要单独处理并单独设计算法,会大大增加代码复杂度。感兴趣的可以自行研究。若对此题或此类问题有想法或有其他做法的同学,欢迎来与我讨论。这里留下我的联系方式:

E-mail: fizzydavid@qq.com
QQ: 2691291070

其他

题中的主人公pekora和miko是hololive所属的vtuber兔田佩克拉和樱巫女,感兴趣的可以戳:

兔田佩克拉:https://space.bilibili.com/443305053

樱巫女:https://space.bilibili.com/366690056

评论

回复

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。