Source

This problem is adapted from Long Long OJ. All rights reserved.

Attention

is the hard version of this problem.

Problem Description

It is believed that everyone is familiar with the rules of Sokoban:

• The map contains several walls (the area outside the map boundary is also regarded as a wall), several boxes, an equal number of targets, and one player;
• If an adjacent cell is an empty space, the player can move into it;
• If an adjacent cell is a box and the next cell in that direction is an empty space, the player can move one step in that direction and push the box one step forward;
• Both movement and box pushing are in four directions (up, down, left, right);
• The player wins when all boxes are on the targets.

Now, please construct a Sokoban puzzle with a size limit of $\mathbf{20\times 20}$, with exactly one box, and make the number of steps in the optimal solution as large as possible (but not unsolvable).

If the minimum number of steps to complete your puzzle is $\color{red}\ge 114$, your solution is considered correct.

Scoring Details

You will get $0$ points if:

• The number of occurrences of either O or * in your answer is not 1;
• The Sokoban puzzle is unsolvable;
• The minimum number of steps to complete your puzzle is within $\color{red}114$ steps (excluding $\color{red}114$ steps).

Otherwise, you will get $100$ points.

Answer Format

This is an output-only problem.

You need to submit a text file named map.txt.

Your output should be a $\mathbf{20\times 20}$ matrix, where:

• # represents a wall;
• . represents an empty space;
• P represents the player's initial position;
• * represents the box's initial position;
• O represents the target.

(The player's initial position and the target's initial position cannot overlap.)

An incorrect output example:

###..............###
##................##
#..................#
....................
...P................
....................
....................
.......*............
....................
....................
................O...
....................
....................
....................
....................
....................
....................
#..................#
##................##
###..............###