Source

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

Attention

There is a hard version of this problem:

Problem Description

The rules of Sokoban are familiar to everyone:

• The map contains several walls (the area outside the map boundaries is also considered 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 allowed 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 the puzzle must not be unsolvable).

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

Scoring Criteria

You will receive 0 points if:

• The total number of either O or * in your answer is not exactly 1;
• The Sokoban puzzle is unsolvable;
• The minimum number of steps to complete your puzzle is within 114 steps (excluding 114 steps).

Otherwise, you will receive 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 must not overlap.)

An example of an incorrect output:

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