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

· · 题解

题目

P14614 [2019 KAIST RUN Fall] Bigger Sokoban 40k

题意

其实题目说得很清楚了，我再写一遍。

设置一个更大推箱子网络，要求满足：

  1. 至少 40,000 步才能解决。
  2. 有且仅有一个箱子及目标位置。
  3. 长和宽以及他们的和要大于等于一，但不能超过一百。
  4. 玩家、箱子和目标位置必须互不重叠。
  5. 尺寸为 2\times2。

    分析

    神秘紫色构造题一枚。

观察题目给的样例：

5 6
....SS
....SS
.#BB#.
..BB.P
......

由于长、宽有要求，故图要小。

但是步数要求很大，我们需要不断绕圈子来推箱子。

箱子和指定地点应该放在两个角，从而使距离足够远。

我们把尽可能多的绕很多圈子的形状拼接起来即可。如下面这样的图案：

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

或者这样的：

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

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    cout<<51<<" "<<47<<endl;
    printf(
        ".....##########################################\n"
        ".##P.##...#.............#...#.............#...#\n"
        ".#.BB.....#.................#.................#\n"
        ".#.BB.....#.................#.................#\n"
        ".#....#...##..#.........#...##..#.........#...#\n"
        ".######..###..###########..###..###########..##\n"
        ".#...##..##...#....#...##..##...#....#...##..##\n"
        ".#........#........#........#........#........#\n"
        ".#........#........#........#........#........#\n"
        ".#...#....#...##..##...#....#...##..##...#....#\n"
        ".##..###########..###..###########..###..######\n"
        ".##..##...#....#...##..##...#....#...##..##...#\n"
        ".#........#........#........#........#........#\n"
        ".#........#........#........#........#........#\n"
        ".#....#...##..##...#....#...##..##...#....#...#\n"
        ".######..###..###########..###..###########..##\n"
        ".#...##..##...#....#...##..##...#....#...##..##\n"
        ".#........#........#........#........#........#\n"
        ".#........#........#........#........#........#\n"
        ".#...#....#...##..##...#....#...##..##...#....#\n"
        ".##..###########..###..###########..###..######\n"
        ".##..##...#....#...##..##...#....#...##..##...#\n"
        ".#........#........#........#........#........#\n"
        ".#........#........#........#........#........#\n"
        ".#....#...##..##...#....#...##..##...#....#...#\n"
        ".######..###..###########..###..###########..##\n"
        ".#...##..##...#....#...##..##...#....#...##..##\n"
        ".#........#........#........#........#........#\n"
        ".#........#........#........#........#........#\n"
        ".#...#....#...##..##...#....#...##..##...#....#\n"
        ".##..###########..###..###########..###..######\n"
        ".##..##...#....#...##..##...#....#...##..##...#\n"
        ".#........#........#........#........#........#\n"
        ".#........#........#........#........#........#\n"
        ".#....#...##..##...#....#...##..##...#....#...#\n"
        ".######..###..###########..###..###########..##\n"
        ".#...##..##...#....#...##..##...#....#...##..##\n"
        ".#........#........#........#........#........#\n"
        ".#........#........#........#........#........#\n"
        ".#...#....#...##..##...#....#...##..##...#....#\n"
        ".##..###########..###..###########..###..######\n"
        ".##..##...#....#...##..##...#....#...##..##...#\n"
        ".#........#........#........#........#........#\n"
        ".#........#........#........#........#........#\n"
        ".#....#...##..##...#....#...##..##...#....#...#\n"
        ".######..###...##########..###...##########..##\n"
        ".#...#.........#...#...#.........#...#...#....#\n"
        ".#...#.........#...#...#.........#...#...#SS..#\n"
        ".#...#....##...#...#...#....##...#...#...#SS..#\n"
        ".############################################.#\n"
        "..............................................#"
    );
    return 0;
}