← 返回题目列表

AtCoder · c_league2026_1_a

A. 抛光和滑动

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

問題文

N\times N 个格子组成的棋盘。 左上角格子的坐标为 (0,0) ,从那里向下 i 格,向右 j 格到的位置的格子坐标为 (i,j) 。

。你是少年工厂 (i_0, j_0) 处,并希望以此顺序访问指定的目的地 (i_1, j_1), \dots, (i_{M-1}, j_{M-1}) 。

每回合中,可以选择并执行以下任意一项行动。

  • 擦拭: 将当前位置的格子擦拭得闪亮。对于未到过的格子不会产生效果。对已经到过的格子进行此操作也不会有任何变化。
  • 滑动: 朝上下左右的方向 d ,重复向该方向移动,直到试图移出棋盘或到达未打磨的格子。更具体地,进行以下重复操作: 如果
    1. d 方向相邻的格子在棋盘外,则停留在当前位置并结束重复。 如果
    2. d 方向相邻的格子未打磨,则移动到相邻格并结束重复。 如果
    3. d 方向相邻的格子已打磨,则移动到相邻格并继续重复。

example

如果一个人通过“滑行”移动到达或经过下一个目的地的某个方格,则认为该点已到达该目的地。 如果在同一“滑溜”移动中按指定顺序通过多个目的地,则所有这些转弯都被视为已访问。 一方面,如果你到达或经过一个尚未被列入访问顺序的目的地空间,那时该区域就不被视为已访问。 轮到你访问目的地后,你必须再次到达或经过该方格。

行动全力 10000 可以一直执行到回合。 寻找一条能让你按顺序、尽可能少回合访问所有目的地的行动路线。

得点

输出动作序列中的回合数 T 评分10000-T 。

如果您无法按顺序访问所有目的地,WA 变为。 给定了

测试用例共有 100 个,每个测试用例的得分总和即为提交的得分。 如果在一个或多个测试用例中出现不正确输出或超出时间限制的情况,则整体判定 WA 或 TLE 变为。 给定了


入力

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

N M
i_0 j_0
\vdots
i_{M-1} j_{M-1}
  • 在所有测试用例中,N=20、M=100 被固定为
  • 少年的位置及目的地坐标 (i_k,j_k) 为0 \leq i_k, j_k \leq N-1 满足条件的整数,且全部互不相同。

出力

每回合的行动用以下方式用字母表示。

  • 擦拭: P
  • 滑动: 根据滑动的方向,上:U、下:D、左:L、右:R

回合数为 T、t 第 n 回合的行动表示的字母为 a_t 时,请按以下格式输出到标准输出。

a_0
\vdots
a_{T-1}

参见示例

入力生成方法

少年位置及目的地会按照以下步骤生成。

首先,所有的 N^2 个格子的坐标按随机顺序重新排列。 在重新排列的坐标列中,从前面开始的 M 个按顺序作为 (i_0,j_0), (i_1,j_1), \dots, (i_{M-1},j_{M-1}) 采用。

工具(输入生成器、可视化器)

在比赛期间,禁止与团队外分享可视化结果或提及解法、涉及内容。请注意。