#P2784. 「BalticOI 2016 Day2」迷宫

「BalticOI 2016 Day2」迷宫

Cannot parse: undefinedms error parsing time

题目描述

题目译自 BalticOI 2016 Day2 T2「Maze」

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

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

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

输入格式

第一行,一个整数 tt,表示数据组数。

接下来 tt 行,每行三个整数 n,mn,mkk,表示迷宫的大小必须为 n×mn \times m 并且刚好有 kk 枚金币。

输出格式

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

2
3 3 1
4 7 2
###
#.x
#o#

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

评分标准

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

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