题解：P14614 [2019 KAIST RUN Fall] Bigger Sokoban 40k

· · 题解

::::info[前记] 本篇题解建议在 个人中心->用户设置->偏好设置->代码字体 选择 Lucida Console 情况下食用。

很恶心棒的一道手搓题目。（如果能可以通过某个代码构造出来，当我没说。） ::::

思路

由于 n+m\le100，若要想最大化走路步数，最优解是 50\times50 的迷宫，但是会根据实际情况会有所不同。

正解可由两个性质得出：

性质 1

推箱子问题很有意思的是：他不能被推到两边都有角落的墙上。例如：

.......
.#####.
.#.BB#.
...BB..
.......

显然，这没有任何方法让它出来，是失败的解法。（除非 S 在这墙边上。）

由性质 1 来看，程序不可能把它推到如上的墙上。

那么我们可以限制箱子的走位了，就不至于让程序使它运行到我们意料之外的地方。

性质 2

箱子也会占位置，人走不过去。

那么我们结合性质 1 就可以得出一种非常强大的解法：

.#P.#.....
.#BB######
.#BB##...#
#........#
#........#
#....#...#
######..##

人向下推两格，肯定不能向下推向下推，否则违背条件 1。那么：

.#..#.....
.#..######
##P.##...#
#.BB.....#
#.BB.....#
#....#...#
######..##

向下又推不了，人走也走不过去，怎么办？

绕路！一个达到 40000 步的关键，否则你单纯让程序绕迷宫顶多 2500 步。

于是它好不容易绕了过来：

.#..#.....
.#..######
##..##...#
#PBB.....#
#.BB.....#
#....#...#
######..##

推三步：

.#..#.....
.#..######
##..##...#
#....PBB.#
#.....BB.#
#....#...#
######..##

得了，又绕一次。好不容易绕完路出去......

.#..#.....
.#..######
##..##...#
#........#
#........#
#....#...#
######..##
#...##.P##
#.....BB.#
#.....BB.#
#...#....#
##..######

你在像我这样多弄一点，弄成接近 50\times50 的矩阵。

程序直接破防了：那还玩啥了，AC 给你了。（其实你会先比程序破防。）

然后就 AC 了。

完整迷宫图自己画吧，没人知道我画了多久。