U398206 Sokoban Golf

本题是 MIT Mystery Hunt 2024 的 Marathon Block Pushing Game 一题的第二部分。原题的要求是一个至少 1000 步的解。我做了一个 1500 多步的解以后想看看其他人能卷到多少。

推箱子的规则相信大家都不陌生： - 地图上有若干个墙，若干个箱子，相同数量的目标，一个玩家 - 如果相邻的某一格是空格，则可以走上去 - 如果相邻的某一格是箱子，且这个方向的下一格是空位，则可以向那个方向走一步并将箱子推一格 - 行走和推箱子都是四方向的 - 当所有箱子都在目标上时，玩家胜利 现在，请构造一个推箱子谜题，其大小限制为 **20x20**，**箱子只能有一个**，并让最优解步数**尽可能大**（但**不是无解**）。

无输入。

你的输出应当是一个 20x20 的矩阵。用 `#` 代表墙，`.` 代表空地，`P` 代表玩家的初始位置，`*` 代表箱子的初始位置，`O` 代表目标。（玩家和目标的初始位置不能重合。） 一个合法的输出示例请参考样例。 （实际上因为我懒，`#P*O` 以外的字符全都是当空地处理的，你输出空格或者其他什么的也可以。另外不会检查行数是否超过 20 以及每行字符是否超过 20，超过的话会按前 20 行的前 20 个字符作为地图。）

如果你的输出中 `OP*` 之一的出现次数不是 1，或这个推箱子无解，你将得到 0 分。否则，你的分数等于最优步数。例如，样例的得分是 20。 地图的边界外视为墙。 附件为本题使用的 Special Judge，你可以用于自己测试。 --- （1/18 更新）提示 1： 考虑下面这个结构。（问号代表某段未知路径） ``` ????? P ? ##*## ? #....?? #...# ##### ``` 玩家从上方把箱子推进来以后，不得不绕问号路径走一圈再继续前进。 如果让问号路径足够长，那就能增加很多步数。 --- 1/18 更新：更换了之前发大病写的繁琐一万倍还没有优化效果的 SPJ，附件的已同步更新。