loj#P2784. 「BalticOI 2016 Day2」迷宫
「BalticOI 2016 Day2」迷宫
Cannot parse: undefinedms error parsing time
题目描述
题目译自 BalticOI 2016 Day2 T2「Maze」
Uolevi 开发了一个让玩家收集金币的游戏。然而,问题在于这个游戏太简单。你能设计一些有挑战性的迷宫吗?
每个迷宫都是一个只包含地板(.
)和墙(#
)的矩阵。其中有一个格子是起点(x
),并且有些格子是金币(o
)。玩家从起点开始,并且可以向四个方向移动。玩家的目标是收集到所有金币并回到起点。
迷宫的难度定义为满足上述要求的最短路径的长度。
输入格式
第一行,一个整数 ,表示数据组数。
接下来 行,每行三个整数 和 ,表示迷宫的大小必须为 并且刚好有 枚金币。
输出格式
对于每组数据,输出一个迷宫,迷宫之间以空行隔开,且每个迷宫必须有解。
2
3 3 1
4 7 2
###
#.x
#o#
.o.####
.#..x.#
...##.#
###o...
评分标准
请在附加文件中下载 maze.in
,你需要提交答案 maze.out
。
对于每个迷宫,你的分数是 ,其中 为你找到的这个迷宫的难度, 为我们找到的最高的迷宫的难度,你的总得分为所有测试得分四舍五入后的平均值。