题解 P6737 【[BalticOI 2016 Day2] 迷宫】

一只书虫仔 · 2020-08-16 19:33:35 · 题解

Description

构造迷宫，满足构造出来的迷宫下面这道题的答案为 k。

给定一个迷宫，迷宫中有四种方块：

. 地板，可以走

# 墙壁，不可以走，也不可以穿过

x 基地

o 硬币

您的任务就是求从基地开始，可以向上，向下，向左，向右走，最后回到基地得到的硬币数的最大值。

Solution

第一眼，这题太好做了吧？！把硬币攒到一块不就好了。

第二眼看 spj 评分策略，哦，原来是要构造最长路啊（

所以在这里说说最长路的构造方法吧！我翻了翻官方输出文件，大概分为两种构造方法：

对于普通道路，蛇形拐，举个栗子：

#..#...
.#..#..
..#..#.
...#..#

对于要拿硬币的道路，设置一个死胡同，进去出来要从一个道路走，变得不通畅，举个栗子：

.......
....#.#
....#.#
....#.#
...#..#
.##..#.
.#o.##.
.####.

并且能贴边尽量贴边，构造的蛇形拐尽量要一个挨着一个，拿硬币的道路可以和蛇形拐融合在一起。

下面我们来分析数据，数据只有一组让构造 50 个迷宫的数据，我们先来分析五组。

Maze 1：n=10,m=18,k=2

对于这种地图很大金币很少的，我们可以把基地放在左上角，然后把金币尽量放右下角，让取完金币后需要再次折返。 ``` ...#.x#...#...#... .#...#..#.#.#.#.#o ..###..#..#.#.#..# #.#...#..#..#..#.. ..#.##..#..###..#. .#..#..#..#...#... .#.#..#..#..#..### .#.#.#..#..###.... .#.#.#.#..#...###. ...#.....#o.#..... ``` Maze 2：$n=11,m=14,k=3

同理。

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

Maze 3：n=9,m=17,k=4

同理。

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

Maze 4：n=8,m=9,k=6

这个迷宫很小，但是金币较多，我们可以采取另外一个策略。

让基地在左侧，金币都在右侧，但是每个或者每两个之前都有很长的墙分隔，所以都需要绕着墙走。

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

Maze 5：n=5,m=11,k=4

同理。

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

不难发现，剩下的和上面 5 个同理，要不就是 n,m 和 k 数量级差别很大，要不就是很少，这里就不一个一个分析了，直接放另外 45 个迷宫的答案了。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ooo#xo
o#o.#.
..#...
#.o#.#
..#...
o#o.#o

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

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

输入文件在题目中有了，就不放了。

这题真是毒瘤的提交答案题（

By Shuchong
2020.8.16