Problem Description

You see a problem.

Given a maze, there are four types of cells in the maze:

• . floor, walkable.
• # wall, not walkable and cannot be passed through.
• x base.
• o coin.

Your task is to find the maximum number of coins that can be obtained starting from the base, moving up, down, left, or right, and finally returning to the base.

You want to know: given the maze size is $n \times m$, and the required answer is $k$, whether you can construct such a maze.

Because you created $t$ such problems, you need to construct $t$ mazes.

Input Format

The first line contains an integer $t$, representing the number of mazes to construct.
The next $t$ lines each contain three integers $n, m, k$, representing the maze size and the final answer.

Output Format

For each test case, output $n$ lines, each containing $m$ characters describing the maze.
There should be a blank line between two mazes.

2
3 3 1
4 7 2

###
#.x
#o#

.o.####
.#..x.#
...##.#
###o...

Hint

Data Description and Scoring Policy

This is an output-only problem. Please obtain the input testdata from the attachment.

There is $1$ set of input and output files with $t=50$. The file in your submitted answer package should be maze.out.

We define:

• The difficulty $x$ of the maze you obtain as the shortest path length to collect all coins starting from the base.
• The difficulty $d$ of the maze obtained by the official solution as the shortest path length to collect all coins starting from the base.

This problem uses a Special Judge. For each constructed maze, you can get a score of

points.

Thanks to the spj provider

Notes

Translated from BalticOI 2016 Day2 B Maze。

Translated by ChatGPT 5