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

· · 题解

写篇题解纪念一下自己第一次考场最快解。

然而手搓完地图后就一题都没写……我真是飞舞。

原题传送门

建议代码字体选用 Lucida Console 以获得更好的阅读体验。

这是一道妥妥的构造题。

我们看到样例输出：

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

明显，图小但是步数大的精髓在于需要不断绕圈子从而推动箱子。

具体的，我们先规划出一条“L”形的走道，宽度为 1，目的是让人通过而箱子过不了。

然后，让箱子 B 和区域 S 分别在地图的两个角落。

接着，设置障碍，让箱子必须不断拐弯，并且使拐点四周宽度尽量为 2，使得角色必须绕走道走一圈才能使箱子“拐弯”。

如果拐点够多的话 n,m=50 基本就能过了。

剩下交给手搓。

所以核心就是要玩过“推箱子”？

code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n = 51, m = 47;
string s[100] = {
    ".......###.#############.###.#############.###.",
    ".##P.##...#.............#...#.............#....",
    ".#.BB.....#.................#.................#",
    ".#.BB.....#.................#.................#",
    ".#....#....#..#.........#....#..#.........#...#",
    "..####...#.#...####.####...#.#...####.###.#..#.",
    ".#...##..##...#....#...##..##...#....#...##..#.",
    ".#........#........#........#........#........#",
    ".#........#........#........#........#.........",
    ".#...#....#...##..#....#....#...##..#....#....#",
    "..#..#.###.###.#..#.#...####.###.#..#.#..#.###.",
    "..#..##...#....#...##..##...#....#...##..##...#",
    ".#........#........#........#........#.........",
    ".#........#........#........#........#........#",
    ".#....#....#..##...#....#....#..##...#....#...#",
    "..####...#.#..#.###.#####..#.#..#####.#####..#.",
    ".#...##..##...#....#...##..##...#....#...##..#.",
    ".#........#........#........#........#........#",
    ".#........#........#........#........#........#",
    ".#...#....#...##..##...#....#...##..#....#....#",
    ".##..#####.#####..#.#..#####.#####..###..#####.",
    ".##..##...#....#...##..##...#....#....#..##...#",
    ".#........#........#........#........#........#",
    ".#........#........#........#........#........#",
    ".#....#...##..##...#....#...##..##...#....#...#",
    "..####...#.#..#####.#####..#.#..#####.#####..#.",
    ".#...##..##...#....#...##..##...#....#...##..#.",
    ".#........#........#........#........#........#",
    ".#........#........#........#........#........#",
    ".#...#....#...##..##...#....#...##..#....#....#",
    "..#..#####.#####..#.#..#####.#####..###..#####.",
    ".##..##...#....#...##..##...#....#....#..##...#",
    ".#........#........#........#........#........#",
    ".#........#........#........#........#........#",
    ".#....#...##..##...#....#...##..##...#....#...#",
    "..#####..#.#..#####.#####..#.#..#####.#####..#.",
    ".#...##..##...#....#...##..##...#....#...##..#.",
    ".#........#........#........#........#........#",
    ".#........#........#........#........#........#",
    ".#...#....#...##..##...#....#...##..#....#....#",
    "..#..#####.#####..#.#..#####.#####..###..#####.",
    "..#..##...#....#...##..##...#....#....#..##...#",
    ".#........#........#........#........#........#",
    ".#........#........#........#........#........#",
    ".#....#...##..##...#....#....#..##...#....#...#",
    "..###.#..#.#....###.#####..###...##########..#.",
    ".#...#.........#...#...#.........#...#...#....#",
    ".#...#.........#...#...#.........#...#...#SS..#",
    ".#...#....##...#...#...#....##...#...#...#SS..#",
    "..###.#####.###.###.###.####.####.###.###.###.#",
    "..............................................#"};

int main() {
    printf("%d %d\n", n, m);
    for (int i = 0; i < n; i++) {
        cout << s[i] << endl;
    }
}