← 返回题目列表

AtCoder · masters2025_qual_a

A. 矿石轧制 (A)

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

问题陈述

有一个洞穴,由 N \times N 网格。 让 (0,0) 是左上角正方形的坐标,并且 (i,j) 是所在正方形的坐标 i 向下平方并 从那里向右走 j 方块。 洞内四周有围墙,无法向外移动。

洞内有岩石, M 矿石类型散布在网格中。 此外,还有 M 包含孔的不同方块,您需要掉落所有该类型的矿石 i 进入 i第一个洞。 岩石可能会掉落到任何洞中或留在洞穴内。 您最多可以执行以下操作 10000 次。

  1. 沿四个方向(上、下、左、右)移动到相邻的方格。 即使目标方格包含洞、岩石或矿石,您也可以移动。
  2. 将当前位置的岩石或矿石运送到四个方向中任意一个方向的相邻方格。 目的地不得包含其他岩石或矿石。目的地可能是一个洞。 如果目的地是一个洞,岩石或矿石会落入其中并被移除。您的位置移动到目标方块。
  3. 将当前位置的岩石或矿石向四个方向之一滚动。滚动的岩石或矿石继续沿直线移动,直到与岩石、矿石或墙壁碰撞,或落入洞中。你的立场不会改变。

通过以下重复步骤更详细地处理滚动操作:

  1. 如果滚动方向上的相邻方块是孔,则岩石或矿石落入其中并被移除。
  2. 如果滚动方向上的相邻方格包含岩石或矿石,或者位于范围之外 N \times N 格子,岩石或矿石停在当前方格。
  3. 否则,它会移动到相邻的方块并重复该过程。

滚动速度非常快,因此岩石或矿石总是会在你的下一个动作之前停止或落入洞中。

你的目标是使用尽可能少的动作将所有矿石放入相应的洞中。

评分

让 T (\leq 10000) 是输出动作序列的长度, K 是初始网格中的矿石总数,并且 A 是成功投入正确孔中的矿石总数。分数计算如下:

  • If A = K,则得分为 \mathrm{round}(10^6 \times (1+\log_2{\frac{10000}{T}})).
  • If A < K,则得分为 \mathrm{round}(10^6 \times \frac{A}{K}).

根据不同的输入生成方法,该问题分为三个子问题:A、B、C。 每个子问题包含 150 个测试用例,提交该子问题的总分是该子问题中所有测试用例得分的总和。 如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判断为 WA or TLE ,提交的分数将为零。

最终排名由各子题获得的最高分之和决定,赛后不进行系统测试。 如果有多支队伍获得相同分数,则无论提交时间如何,他们都将排名在同一位置。


输入

输入由标准输入按以下格式给出:

N M
C_0
\vdots
C_{N-1}
  • 网格大小 N 固定为 N = 20 适用于所有测试用例。
  • 矿石种类数量 M 对于每个子问题都是固定的。请参阅 “输入生成” 部分了解详细信息。
  • 对于每个 i = 0, 1, \dots, N-1, C_i 是一个长度为的字符串 N,其中 j- 第一个字符代表方块的初始状态 (i, j) 如下:
    • @:存在一块岩石。
    • a-z:存在矿石。
    • A-Z:存在一个孔。
    • .:广场是空的。

矿石和洞根据大小写字母对应。 例如,用字符表示的矿石 a 对应字符代表的孔 A。 第一个 使用 M 字母表中的字母。同一类型的矿石可能有多种,但每种类型恰好有一个孔。

你从包含孔的正方形开始 A 处于初始状态。

输出

步骤中的操作 t 由一对表示 (a_t, d_t),其中 a_t \in \{1,2,3\} 表示动作类型(1:移动,2:进位,3:滚动), d_t \in \{U,D,L,R\} 代表方向(上、下、左、右)。

例如, (3, R) 表示将当前位置的岩石或矿石向右滚动的动作。

然后,按以下格式输出到标准输出。

a_0 d_0
\vdots
a_{T-1} d_{T-1}

示例解决方案

提供了 Python 示例解决方案。 该程序将位于初始位置右侧的岩石或矿石带入孔中,并将位于初始位置下方的岩石或矿石滚入孔中。 所有其他岩石和矿石均未受影响。
N, M = map(int, input().split())
grid = [list(input()) for _ in range(N)]

# Retrieve the current position
pi = 0
pj = 0
for i in range(N):
    for j in range(N):
        if grid[i][j] == 'A':
            pi = i
            pj = j

# Move to the right and carry any rock or ore found into the hole
for j in range(pj + 1, N):
    if grid[pi][j] == '@' or 'a' <= grid[pi][j] and grid[pi][j] <= 'z':
        print('1 R\n' * (j - pj), end='')
        print('2 L\n' * (j - pj), end='')
    elif 'A' <= grid[pi][j] and grid[pi][j] <= 'Z':
        break

# Move downward and roll any rock or ore found into the hole
for i in range(pi + 1, N):
    if grid[i][pj] == '@' or 'a' <= grid[i][pj] and grid[i][pj] <= 'z':
        print('1 D\n' * (i - pi), end='')
        print('3 U\n', end='')
        pi = i
    elif 'A' <= grid[i][pj] and grid[i][pj] <= 'Z':
        break

输入生成

每个子问题的输入生成方法都不同。 输入的粗略生成如下表所示。

子问题 M 岩石
A 1 很少
B 3 无
C 1 很多

子问题A

M = 1 已修复。

  • 孔的放置 A: 随机选择一个方格 N^2 方块。
  • 矿石的放置 a: 随机选择 剩余的 2N 方格 N^2 - 1 方块。
  • 岩石的放置 @: 随机选择 剩余的 2N 方格 N^2 - 1 - 2N 方块。

子问题B

M = 3 已修复。

  • 孔的放置 A, B,和 C:从中随机选择三个不同的方块 N^2 方块。
  • 矿石的放置 a: 随机选择 剩余的 N 方格 N^2 - 3 方块。
  • 矿石的放置 b: 随机选择 剩余的 N 方格 N^2 - 3 - N 方块。
  • 矿石的放置 c: 随机选择 剩余的 N 方格 N^2 - 3 - 2N 方块。

最后,确保 从每个洞中,仅穿过空方块或包含该矿石的方块就可以到达所有相应的矿石。 如果存在无法到达的矿石,则重复生成过程。


子问题C

M = 1 已修复。

  • 岩石的放置 @:对于每个方块 (i, j),生成 h_{i,j} = \mathrm{noise}(i/10, j/10)。在这里, \mathrm{noise}(y, x) 是一个生成二维的函数 柏林噪音。顶部 N^2/2 最高的方格 h_{i,j} 值被指定为岩石。

  • 孔的放置 A:从剩余的方块中随机选择一个方块 N^2/2 方块。

  • 矿石的放置 a: 随机选择 剩余的 2N 方格 N^2/2 - 1 方块。

工具(输入生成器和分数计算)

请注意,比赛期间禁止在团队之外分享可视化结果或讨论解决方案/想法。


示例输入 1

20 1
..a.@....a.....a....
..@........@..a.@a@.
..aa...a..@.....a...
.............a.....@
.....@.a.....a@@....
..a..a@..a......@...
.@a.@aa...........a@
...............@.a..
.a......@@@.a.......
........@.@..a.....a
.a.A..a....@....a..@
......@..@@.........
..@@....a..@@.a.....
......a.....@..a....
...................a
@@.....@....a.a.a...
.....@.......a...@..
...@......@...a....a
............a..@....
.......a.@..........

示例输出 1

1 R
1 R
1 R
2 L
2 L
2 L
1 R
1 R
1 R
1 R
1 R
1 R
1 R
1 R
2 L
2 L
2 L
2 L
2 L
2 L
2 L
2 L
1 R
1 R
1 R
1 R
1 R
1 R
1 R
1 R
1 R
1 R
1 R
1 R
1 R
2 L
2 L
2 L
2 L
2 L
2 L
2 L
2 L
2 L
2 L
2 L
2 L
2 L
1 R
1 R
1 R
1 R
1 R
1 R
1 R
1 R
1 R
1 R
1 R
1 R
1 R
1 R
1 R
1 R
2 L
2 L
2 L
2 L
2 L
2 L
2 L
2 L
2 L
2 L
2 L
2 L
2 L
2 L
2 L
2 L
1 D
1 D
3 U
1 D
1 D
1 D
1 D
1 D
3 U