P6737 [BalticOI 2016] Maze (Day2)

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.

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.

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

#### 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 $$\max(0,100-3(d-x))$$ points. Thanks to the spj provider @[tiger2005](https://www.luogu.com.cn/user/60864)。 #### Notes Translated from [BalticOI 2016 Day2 B Maze](https://boi.cses.fi/files/boi2016_day2.pdf)。 Translated by ChatGPT 5