← 返回题目列表

AtCoder · future_contest_2020_qual_a

A. 机器人引导

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

問題文

N × N 在格子中,M 台机器人,B 个方块,1 个目标格。

每个格子都有坐标,左上角格子的坐标是 (0, 0),右上角格子的坐标是 (0, N - 1),右下角格子的坐标是 (N - 1, N - 1) 。该格子的左端和右端、上端和下端分别相连,例如格子 (3, 0) 的左邻格是 (3, N - 1)、马斯 (N - 1, 5) 的正下方格是 (0, 5) 。

各罗博托 i (1 \leq i \leq M) 关于,源 (ry_i, rx_i) 与方向的少年值 c_i 。c_i 是 仅由 U, D, L, R 是其中之一,分别表示上下左右。

另外,还会给出每个方块格子和目标格的坐标。i 第几个方块格(1 \leq i \leq B)的坐标是 (by_i, bx_i),目标格的坐标是 (gy, gx) 。

你可以选择若干个格子,并在它们上面设定 方向案内 ,每个方向指示都需要指定上下左右的一个方向。1 无法在一个格子上设置多个方向指示。

方向指示设置完成后,每个机器人会各自重复以下动作。机器人之间不会发生冲突。

  • 当位于目标格时:在该位置停止。
  • 在非这种情况下:首先,如果当前所在的格子上设置了方向指示,就将自己的朝向改为指定的方向。随后,向自己朝向的方向 1 移动格子(注意格子的左端与右端、上端与下端是相连的)。但是,如果移动到的格子是块格子,则移动失败,并停留在原地。

请尽可能让能够在有限次数动作内到达目标格子的机器人数量增加。使用的方向指示越少,机器人经过的格子越多,将获得更高的分数。详细情况请确认“输出”部分。

【注意】在本问题中,不需要求“最优解”。例如,不必让所有机器人都到达目标,也不必将方向指示数量最小化。

制約

  • N = 40
  • M = 100
  • B = 300
  • 0 ≦ gy, gx ≦ N - 1
  • 0 ≦ ry_i, rx_i ≦ N - 1
  • c_i 是 仅由 U, D, L, R 为其中之一。
  • 0 ≦ by_i, bx_i ≦ N - 1
  • 方块格子不会与机器人、目标格子或其他方块格子重叠。(机器人之间或机器人与目标格子之间有时可能重叠)
  • 在满足以上否定条件的范围内,方块格子、目标格子、机器人所在的格子都是均匀随机选取的存在。

入力

输入采用以下格式给出。

N M B
gy gx
ry_1 rx_1 c_1
ry_2 rx_2 c_2
:
ry_M rx_M c_M
by_1 bx_1
by_2 bx_2
:
by_B bx_B

出力

设置的方向指示的数量 K、i 设置第几个方向指示的坐标 (Y_i, X_i)、i 指定给第几个方向指示的方向 R_i (U, D, L, R 是上述任意一项,对应上下左右,按以下格式输出。

K
Y_{1} X_{1} R_1
Y_{2} X_{2} R_2
:
Y_{K} X_{K} R_K

如果不满足上述格式,有时会判定为“不正确”。例如,字符串数量不匹配或使用了指定以外的字符。

此外,即便在同一格子上设置多个方向指示,也会判定为不正确。但在目标格子或方块格子上设置方向指示不会判定为不正确。

测试用例 50 将给定的个数。对于每个测试用例,能够在有限次数的动作中到达目标的机器人数量为 A,设置的方向指示数量为 B,机器人即便短暂经过的格子数量为 C ,则该测试用例中 1000 \times A - 10 \times B + C 点将被取得。全部测试用例的总分为该提交的得分。

如果产生了不正确的输出,并且该测试用例属于给定的输入示例,则该测试用例的得分为 0 点。对于其他测试用例,输入示例之外的所有测试用例的得分为 0 点。

入出力例

输入示例和输出示例可以 从该库 下载。