2784 「BalticOI 2016 Day2」迷宫

题目译自 BalticOI 2016 Day2 T2「Maze」

Uolevi 开发了一个让玩家收集金币的游戏。然而，问题在于这个游戏太简单。你能设计一些有挑战性的迷宫吗？

每个迷宫都是一个只包含地板（.）和墙（#）的矩阵。其中有一个格子是起点（x），并且有些格子是金币（o）。玩家从起点开始，并且可以向四个方向移动。玩家的目标是收集到所有金币并回到起点。

迷宫的难度定义为满足上述要求的最短路径的长度。

第一行，一个整数 $t$，表示数据组数。

接下来 $t$ 行，每行三个整数 $n,m$ 和 $k$，表示迷宫的大小必须为 $n \times m$ 并且刚好有 $k$ 枚金币。

对于每组数据，输出一个迷宫，迷宫之间以空行隔开，且每个迷宫必须有解。

第一个迷宫的难度为 $4$，第二个迷宫的难度为 $18$。

请在附加文件中下载 maze.in，你需要提交答案 maze.out。

对于每个迷宫，你的分数是 $\max(0,100-3(d-x))$，其中 $x$ 为你找到的这个迷宫的难度，$d$ 为我们找到的最高的迷宫的难度，你的总得分为所有测试得分四舍五入后的平均值。