← 返回题目列表

AtCoder · rco_contest_2018_qual_a

A. 游戏解说X的挑战

中文机器翻译题面 查看原题

問題文

X,作为一名受欢迎的游戏评论员而活跃,正在致力于创作新视频。这次,我决定尝试一款益智游戏。

这个游戏的目的是 H行W目标是通过在由方格列组成的地图上移动玩家来收集尽可能多的硬币。详细规则如下。请注意地图的最上面一行 0 行,最左边的列 0 栏。

  • 地图上的每个方格要么是墙方格、硬币方格、陷阱方格或空方格。
  • 地图的外周(0线·H-1线·0专栏/W-1柱)是一个墙正方形
  • 初始状态下,只有一个空方格,并且里面有一个玩家。
  • 使用单个命令,您可以将玩家向上、向下、向左或向右移动到相邻的方格。
    • 如果目的地是墙方格,则不要移动并留在当前方格中。
    • 如果玩家落在硬币方块上,他会得到一枚硬币。硬币从那个方格中消失,它变成了一个空的方格。
    • 如果玩家进入陷阱方格,玩家将无法再移动。
  • 命令最大。 可以给予 T 次

在这个游戏中有 N 地图可用。认为仅仅获得高分并不好玩,X 决定接受下一个挑战。 来自

  • N 地图 选择 K 地图
  • 那些 使用相同的命令操作 K 地图

决定如何选择地图以及执行哪些命令以最大化您可以获得的硬币总数。

各 tstokeesu 的得分以及本题的得分按如下方式计算。

  • 选择一个测试用例的分数 在 K 地图上获得的金币总数。
  • 总共 30 个存在。各 tstoke-su 的得分总和,将作为本题的得分。

入力

输入是按以下格式从标准输入给出的。

N K H W T
row_{0,0}
row_{0,1}
:
row_{0,H-1}
row_{1,0}
:
row_{N-1,H-1}
  • N 是表示地图数量的整数, 满足N=100 满足
  • K 是一个整数,表示要使用的地图数量,K=8 满足
  • H 是一个整数,表示地图中的行数,H=50 满足
  • W 是一个整数,表示地图中的列数,W=50 满足
  • T 是一个整数,表示最大命令数, 地图的T=2,500 满足
  • row_{i,j} 是 您也可以写 i 第二张地图的 j 代表行 W 一串字符。每个字符都是#, o, x, @ 。
    • # 代表墙方。
    • o 代表硬币方块。
    • x 代表陷阱方块。
    • @ 代表玩家所在的方格。
    • 每张地图的外周长是 # 有保证。
    • 对于每张地图 仅保证存在一个 @ 。

出力

在第一行中,输入代表所选地图编号的整数(从 0 开始)。 请输出 K ,以空格分隔。

第二行表示要执行的命令字符串。 请输出小于或等于 T 个字符的字符串。

M_0 M_1 … M_{K-1}
commands
  • M_0, M_1, …, M_{K-1} 彼此不同。 小于 0 以上 N 的整数。
  • commands 可以得到第 i 第一个字符是i 命令。
  • 每个命令由以下字符表示。
    U
    移动到比当前方格小一行的方格。 (向上移动)
    D
    移动到比当前方格大一行的方格。 (向下移动)
    L
    移动到比当前方格小一行的方格。 (向左移动)
    R
    移动到比当前方格大一行的方格。 (向右移动)

关于 tstokesu 的生成

每个地图都是通过以下步骤生成的:

  • 使外围成为墙正方形
  • 除外围以外的每个方格都有一个概率 0.77 到硬币方块,概率 0.20 到墙方,概率 使用 0.03 使其成为陷阱方块。
  • 选择边界外的一个方格并将其替换为空方格(玩家最初所在的方格)

入力例1

4 2 8 8 3
########
#o#oooo#
#ooooo##
##ooooo#
#oooo#x#
##o#ooo#
##@ooox#
########
########
##xoooo#
#oo#oox#
#oooooo#
#oooxoo#
##o@o#o#
#o#oo#o#
########
########
#ooo##o#
#oo##oo#
#ooo@oo#
###oooo#
#o#xo#o#
#ooooo##
########
########
#ooo#oo#
##oooo##
##ooo#@#
#oooooo#
#oo#ooo#
#oooo#x#
########

注意:此输入不满足作为 tstokesu 的否定条件。

地图如下所示。

出力例1

1 2
URR

我选择了地图 1 和地图 2。运行所有命令后,地图将如下所示:

  • 第一个命令使地图 1 上的玩家向上移动并获得金币。地图 2 上的玩家不会移动,因为顶部是墙。
  • 第二个命令使地图 1 上的玩家向右移动并进入陷阱方块。地图 2 玩家向右移动并获得金币。
  • 在第三个命令中,地图 1 上的玩家无法移动,因为他位于陷阱方块中。地图 2 玩家向右移动并获得金币。
  • 由于您在地图 1 上获得 1 个硬币,在地图 2 上获得 2 个硬币,因此您在此测试用例中获得的分数为 3 分。

发生器和测试仪

我们在以下链接提供测试用例生成器和测试器。

发电机测试仪


展示台

我们准备了一个可视化工具,可以计算分数并可视化输入和输出文件的结果。

  • 此可视化工具已经过测试,可在主要浏览器上运行,但不能保证在所有环境中都能运行。特别是,已经确认它不能在 Internet Explorer 上运行。
  • 此可视化工具上计算的分数不是本次比赛的分数。评分将通过在 AtCoder 上提交答案来完成。此外,在可视化工具上计算的分数并不能保证您在本次比赛中的分数。
  • 请注意,我们不能保证因使用此可视化仪而造成的任何损坏。

还可以通过以下链接获取该可视化工具。链接中还包含有关如何使用它的说明。

展示台

观察仪主体
fps
  • 壁 : ■
  • 硬币: ■
  • 罠 : ■
  • 玩家: ■
将绘图内容保存为图像