问题陈述
有一个 N\times N 网格。 左上角的单元格有坐标 (0,0),并且通过移动到达的单元格 i 细胞下降并且 j 右侧的单元格有坐标 (i,j).
N 是偶数,并且对于每个数字 0 to \frac{N^2}{2}-1,恰好有两张牌具有该数字。 最初,将这些卡片中的一张准确地放置在每个单元上。
你从位置开始 (0,0) 使用空甲板并重复以下操作:
- 移动到四个方向(上、下、左或右)之一的相邻单元格。你不能走出 N\times N 网格。
- 如果你当前位置有一张卡,你可以将其移至你的牌库顶。如果这副牌中最上面的两张牌的数字相同,那么这两张牌就会从这副牌中移除。
- 如果你当前位置没有卡牌,你可以将你牌库最上面的卡牌放到当前格子上。如果你的牌组是空的或者当前单元格中已经有一张牌,则无法执行此操作。
您最多可以执行 2N^3 操作。 您的目标是从网格和牌组中移除所有牌。 找到最小化次数的操作序列 移动。 请注意,执行操作 2 和 3 的次数计入操作限制,但不计入评估分数。
评分
让 K 是输出操作序列中的移动次数,并让 X 是最后网格上和牌组中剩余的牌数。您的分数计算如下:
- If X=0,那么你的分数是 N^2 + 2N^3 - K
- If X>0,那么你的分数是 N^2 - X
输入
输入由标准输入按以下格式给出:
N
a_{0,0} \cdots a_{0,N-1}
\vdots
a_{N-1,0} \cdots a_{N-1,N-1}
- 在所有测试用例中, N = 20 已修复。
- a_{i,j} 代表最初放置在单元格的卡上写的数字 (i,j),并且是满足的整数 0 \leq a_{i,j} \leq \frac{N^2}{2} - 1.
- 每个值 a_{i,j} 恰好出现两次。
输出
依次进行每个操作 t 由单个字符表示 c_t 如下:
- 对于操作 1(移动),请使用方向: 向上:
U,向下:D,左:L,右:R - 对于操作 2(拾取):
Z - 对于操作 3(地点):
X
让 T 是操作总数。将结果按以下格式输出到标准输出:
c_0
\vdots
c_{T-1}
输入生成
卡片的初始放置 a_{i,j} 是通过随机洗牌所有生成的 N^2 卡。
工具(输入生成器和可视化工具)
- 网页版:这比提供动画和手动播放的本地版本更强大。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。