故事
今天,2 月 2 日,日本的传统活动 节分 日本正在庆祝 。 节分是在季节交替时驱除邪灵、祈求好运的仪式。 人们高呼“Oni wa soto!” (“鬼出来!”)一边扔烤黄豆驱走邪灵(oni),一边高呼“Fuku wa uchi!” (“财神爷进来了!”)欢迎 福野神,吉祥神灵。
高桥正在玩一款名为 “Oni wa Soto,Fuku wa Uchi”,灵感来自节分传统。 这个游戏的目的也是赶走恶魔并邀请福之神。
找到使分数最大化的一系列动作。
问题陈述
有一个 N\times N 方板。 让 (0, 0) 是左上角正方形的坐标,并且 (i, j) 是所在正方形的坐标 i 向下平方并 从那里向右走 j 方块。 正方形的集合 (i,0), (i,1), \dots, (i,N-1) 被称为 行 i,以及正方形集合 (0,j), (1,j), \dots, (N-1,j) 被称为 栏目 j.
最初,有 鬼(恶魔)
和 福神(财神)
棋盘上的棋子,带有 2N 每种类型的棋子,都放置在不同的方块上。
您可以在一次操作中选择一行或一列,并将所选行/列向左/右或上/下方向移动一格。
- 移动行 i 左边:正方形上的棋子 (i,0) 从板上移除,并且对于每个 j=1, \dots, N-1,正方形上的棋子 (i,j) 移至 (i,j-1).
- 移动行 i 右边:正方形上的棋子 (i,N-1) 从板上移除,并且对于每个 j=0, \dots, N-2,正方形上的棋子 (i,j) 移至 (i,j+1).
- 移动列 j 向上:正方形上的棋子 (0,j) 从板上移除,并且对于每个 i=1, \dots, N-1,正方形上的棋子 (i,j) 移至 (i-1,j).
- 移动列 j 向下:正方形上的棋子 (N-1,j) 从板上移除,并且对于每个 i=0, \dots, N-2,正方形上的棋子 (i,j) 移至 (i+1,j).
您最多可以执行 4N^2 操作。
你的目标是用尽可能少的步数从棋盘上移除所有鬼,而不移除任何福野神。
评分
让 T 是输出序列中的操作数, X 是棋盘上剩余的鬼数量,并且 Y 是从棋盘上移除的 Fukunokami 的数量。 然后,您将获得以下分数。
- If X=0 和 Y=0,得分为 8N^2 - T.
- If X>0 or Y>0,得分为 4N^2 - N (X+Y).
有 150 测试用例,提交的分数是每个测试用例的总分。 如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判断为 WA or TLE ,提交的分数将为零。 比赛期间获得的最高分将决定最终排名,比赛结束后不进行系统测试。 如果超过一名参赛者获得相同分数,则无论提交时间如何,他们都将排名在同一位置。
输入
输入由标准输入按以下格式给出:
N
C_0
\vdots
C_{N-1}
- 电路板尺寸 N 固定为 N=20 适用于所有测试用例。
- 对于每个 i=0,1,\dots,N-1, C_i 表示行的初始状态 i 作为长度的字符串 N,其中 j-第一个字符是以下字符之一:
x:有鬼在场。o:福野神存在。.:鬼和福神都不存在。
- 正好有 2N 鬼和 2N 福野神在黑板上。
- 对于鬼最初占据的每个方格,至少保证满足以下条件之一。这确保了始终存在最多的序列 4N^2 移动消除所有鬼,同时保留所有福野神在棋盘上。
- 同一列中其上方的所有方块都不包含福野神。
- 同一列中其下方的所有方块都不包含福野神。
- 同一行中其左侧的所有方格都不包含福野神。
- 同一行中其右侧的所有方格都不包含福野神。
提示
对于一个正方形 (i,j) 被鬼占据,如果向上方向没有福野神,则执行向上移动 i+1 次,然后向下移动 i+1 次将移除 Oni (i,j) ,无需删除任何福野神。 同样,如果向下、向左、向右方向没有福之神,则可以使用相应的动作顺序来消除鬼。
由于此操作不会改变棋盘上剩余棋子的位置,因此将其应用于所有 Oni 可确保在不删除任何 Fukunokami 的情况下删除所有 Oni。
输出
步骤中的每个操作 t 表示为一对 (d_t, p_t),其中 d_t 是指示方向的字符, p_t 是一个整数,表示行或列索引。
- 移动行 i 向左:(
L, i) - 移动行 i 向右:(
R, i) - 移动列 j 向上:(
U, j) - 移动列 j 向下:(
D, j)
然后,按以下格式输出到标准输出:
d_0 p_0
\vdots
d_{T-1} p_{T-1}
操作次数 T 不得超过 4N^2。 如果超过限制,输出将被判断为 WA.
输入生成
首先, 2N 不同的方块是从 N^2 板上的方块以确定 2N 福野碎片。
接下来,列出至少满足以下条件之一的所有方格,形成集合 S:
- 同一列中其上方的所有方块都不包含福野神。
- 同一列中其下方的所有方块都不包含福野神。
- 同一行中其左侧的所有方格都不包含福野神。
- 同一行中其右侧的所有方格都不包含福野神。
如果元素的数量 S 小于 2N,重复福野放置过程。
最后, 2N 方块是随机选择的 S 确定的位置 2N 鬼片。
工具(输入生成器和可视化工具)
- 网页版:这比提供动画和手动播放的本地版本更强大。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。