#P12533. [XJTUPC 2025] 9-Nine

    ID: 14086 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>搜索2025Special JudgeO2优化广度优先搜索 BFS构造高校校赛

[XJTUPC 2025] 9-Nine

题目背景

『九次九日九重色,

天色天歌天籁音,

春色春恋春熙风,

雪色雪花雪余痕』

--- 《9-nine-》

题目描述

工艺品(Artifact),白巳津川市自行制作的动画《轮回转生的莫比乌斯环》(虽然收视率极低)中的道具居然来到了现实!拥有它的人都会获得独有的特殊能力,这一切的一切都要从那场地震开始。

「千年之前,本世界和异世界是互通的,而工艺品正是异世界的魔法道具。由于种种原因,出现了一个叫「生命之树」的组织,将所有的工艺品回收后设下了法阵,阻止了两个世界的流通。但是由于地震,法阵被破坏,于是工艺品便流向了这个世界。」------来自异世界的玩偶索菲提娅如是说道。

在索菲的帮助下,我们的主角新海翔带领四位女主与反派进行激烈的斗争,最终成功阻止其使用工艺品犯下不可饶恕的错误。不过,为了根除这个问题,新海翔和索菲决定断绝两个世界的联系,重新打开封印。

封印的法阵可以看做两个 9×99 \times 9 的黑白方阵,新海翔和索菲分别可以控制一个方阵,他们可以做如下动作:

  • 新海翔将自己面前的方阵向左或向右旋转 9090 度;
  • 索菲将自己面前的方阵向左或向右旋转 9090 度(两个方阵不联动);
  • 新海翔和索菲选择方阵的同一列,进行交换;

当新海翔一侧的方阵全是白色,同时索菲一侧的方阵全是黑色,那么封印就完成了,法阵将会开启,断开两个世界的联系,大家可以回归正常生活。

时间有限,请你------我们的「第九人(Nine)」,帮助他们在 999999 步内完成这个封印。

话虽如此,但是出题人被警告题出太难了,所以决定缩小数据范围!

具体的,将方阵的边长减小至 33,同时步数减小至 9×9=819\times 9=81

形式化地说,有两个 3×33 \times 3 的 01 矩阵 AABB,你可以做如下操作:

  • 操作 11:选择矩阵 AABB,将其向左或向右旋转 9090 度;
  • 操作 22:选择一个整数 kk (1k31 \le k \le 3),将两矩阵的第 kk 列交换。

请在 8181 次操作内将 AA 变为全 0 矩阵。数据保证此时 BB 一定为全 1 矩阵。

输入格式

131 \sim 3 行,每行是一个长度为 33 的 01 字符串,表示矩阵 AA 的初始状态;

464 \sim 6 行,每行是一个长度为 33 的 01 字符串,表示矩阵 BB 的初始状态。

数据保证在有限次操作内,可以将 AA 变为全 0 矩阵,BB 变为全 1 矩阵。

输出格式

第一行一个整数 NN (0N810 \le N \le 81),表示你一共需要进行 NN 次操作。

接下来的 NN 行表示你依次进行的操作。请按如下格式输出:

  • 如果你选择使用操作 11,请输出矩阵名与旋转方向。具体地:
    • 若你想将 AA 矩阵向左旋转 9090 度,输出 AL\tt{AL}
    • 若你想将 AA 矩阵向右旋转 9090 度,输出 AR\tt{AR}
    • 若你想将 BB 矩阵向左旋转 9090 度,输出 BL\tt{BL}
    • 若你想将 BB 矩阵向右旋转 9090 度,输出 BR\tt{BR}
  • 如果你选择使用操作 22,请输出 C\tt{C} 与列号。例如,你要交换两个矩阵的第 22 列,请输出 C2\tt{C2}

其中,将一个矩阵向左旋转,指逆时针旋转;将一个矩阵向右旋转,指顺时针旋转。

请注意:不要输出多余的行末空格与文末回车

100
000
000
111
111
011
9
BL
BL
BL
AL
C1
AL
C1
AR
C1

提示

可以证明,在数据合法的情况下,原题在 999999 步内一定存在解,弱化版的题目在 8181 步内一定存在解。

最重要的是还在分割商法的《9-nine-》今年即将推出新作,预计冬季上架某平台。