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

· · 题解

一些闲话

也是被 C 题硬控了一个半小时，这里强烈建议不要再赛场上死磕一道题，后面还是有很多简单题的。

题目分析

我们注意到，箱子大小是 2×2，人的大小是 1×1，所以怎么让玩家走足够多的步数呢，那就得构造大量箱子无法直接被推过去，玩家需要绕极远的路才能抵达的形状。

我们可以尝试构造下面的图形：

// 构造类似于这样的形状就行，为什么呢？
// 很显然，由于规则限制，玩家为了改变推箱子的方向，就必须绕过整个地图，那么这样就能保证步数最大化的条件。
// 我们需要做的就是把尽量多的这种形状拼接起来，可以使用excel表格画一下。
auto maze = {
".....#.."
".##P.##."
".#.BB.SS"
".#.BB.SS"
".#....#."
".######."
"........"
};

那么这道题就很简单了。

AC Code

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

int main()
{
    // 迷宫数据
    string maze[] = {
        ".....##########################################",
        ".##P.##...#.............#...#.............#...#",
        ".#.BB.....#.................#.................#",
        ".#.BB.....#.................#.................#",
        ".#....#...##..#.........#...##..#.........#...#",
        ".######..###..###########..###..###########..##",
        ".#...##..##...#....#...##..##...#....#...##..##",
        ".#........#........#........#........#........#",
        ".#........#........#........#........#........#",
        ".#...#....#...##..##...#....#...##..##...#....#",
        ".##..###########..###..###########..###..######",
        ".##..##...#....#...##..##...#....#...##..##...#",
        ".#........#........#........#........#........#",
        ".#........#........#........#........#........#",
        ".#....#...##..##...#....#...##..##...#....#...#",
        ".######..###..###########..###..###########..##",
        ".#...##..##...#....#...##..##...#....#...##..##",
        ".#........#........#........#........#........#",
        ".#........#........#........#........#........#",
        ".#...#....#...##..##...#....#...##..##...#....#",
        ".##..###########..###..###########..###..######",
        ".##..##...#....#...##..##...#....#...##..##...#",
        ".#........#........#........#........#........#",
        ".#........#........#........#........#........#",
        ".#....#...##..##...#....#...##..##...#....#...#",
        ".######..###..###########..###..###########..##",
        ".#...##..##...#....#...##..##...#....#...##..##",
        ".#........#........#........#........#........#",
        ".#........#........#........#........#........#",
        ".#...#....#...##..##...#....#...##..##...#....#",
        ".##..###########..###..###########..###..######",
        ".##..##...#....#...##..##...#....#...##..##...#",
        ".#........#........#........#........#........#",
        ".#........#........#........#........#........#",
        ".#....#...##..##...#....#...##..##...#....#...#",
        ".######..###..###########..###..###########..##",
        ".#...##..##...#....#...##..##...#....#...##..##",
        ".#........#........#........#........#........#",
        ".#........#........#........#........#........#",
        ".#...#....#...##..##...#....#...##..##...#....#",
        ".##..###########..###..###########..###..######",
        ".##..##...#....#...##..##...#....#...##..##...#",
        ".#........#........#........#........#........#",
        ".#........#........#........#........#........#",
        ".#....#...##..##...#....#...##..##...#....#...#",
        ".######..###...##########..###...##########..##",
        ".#...#.........#...#...#.........#...#...#....#",
        ".#...#.........#...#...#.........#...#...#SS..#",
        ".#...#....##...#...#...#....##...#...#...#SS..#",
        ".############################################.#",
        "..............................................#"
    };

    cout << "51 47" << endl;

    for (const auto& line : maze)
        cout << line << endl;

    return 0;
}