算法逻辑 / base-sliding-maze
Advanced

滑动迷宫

在不断变化的迷宫中规划一条合法路径。

思维能力搜索路径规划构造

一只机器鼠被困在一座会变形的二维迷宫中。它能在通道里正常行走,也能通过循环滑动某一行或某一列来重排迷宫;不过,为了避免把鼠一起带走,不能滑动鼠当前所在的行或列。

格子坐标记为 (r,c)r 从上到下编号,c 从左到右编号,均从 0 开始。鼠从左上角 (0,0) 出发,目标是到达右下角 (n-1,m-1)。你不需要找最短路径;只需给出一条符合限制的操作序列。

迷宫编码

每个格子用 4 位二进制数描述,四位依次表示上、右、下、左四个方向。某一位为 1 表示该方向有开放通道,为 0 表示封闭。将这 4 位按通常二进制数转换为一个十六进制字符。

一个 n×m 迷宫由长度为 n×m 的十六进制字符串给出:前 m 个字符是第一行,接下来的每 m 个字符依次表示下一行。

在一次迷宫状态中,鼠可以沿开放通道移动到从当前位置可达的任意格子,也可以选择不移动。每次重排操作执行前和执行后,鼠都可以进行这样的移动。

可以把一次操作理解为两个阶段:先让鼠在当前迷宫内走到合适位置;再选择一条不经过鼠的行或列循环滑动一格;滑动后,鼠再根据新的通道继续走。后面的列表会把“鼠移动到哪里”和“滑动哪一行或列”按发生顺序写出来。

重排操作

每次操作选择一行或一列,并将其循环移动一个格子:

  • 一行向右移动时,该行所有格子右移一格,最右侧格子从最左侧重新进入;向左移动同理。
  • 一列向下移动时,该列所有格子下移一格,最下侧格子从最上侧重新进入;向上移动同理。
  • 格子与自身的通道编码一起移动。行只能左右移动,列只能上下移动。
  • 严禁移动鼠当前所在的行或列。若鼠位于第 r 行,就不能移动第 r 行;若鼠位于第 c 列,就不能移动第 c 列。

UjDjLjRj 分别表示第 j 列上移、第 j 列下移、第 j 行左移、第 j 行右移一格。

答案用一个列表表示。列表中的坐标项 (r,c) 表示鼠在当前迷宫状态下从之前的位置合法移动到该格;字符串项表示下一次重排。下面的例子先让鼠走到 (3,5),再滑动第 2 列和第 4 行;此时鼠不在这两条线内,所以两次滑动都允许。

text
[(3,5), "D2", "L4", (6,3), "R0", (7,7)]

接着,鼠移动到 (6,3),滑动第 0 行,最后到达 (7,7)。其中字符串项共有 3 个,因此进行了 3 次重排。坐标项可以省略,表示鼠在相邻两次重排之间保持原位。

反例:[(3,5), "D2", "L3"] 是非法的,因为执行 L3 时鼠仍位于第 3 行。

主任务

下面给出一个 15×15 迷宫:

text
593eaacd395ac6eac5a556aa53e3d539bac799c65a5a33da69663a3a33c635a635c3535c95696aa67b3cd3c576993576559db7aaa3655ac5753a933b593eabeca599965ac5a363a3c3d6acaa37cce3c9ecc3cb6397b99b66aa6e37ac9c55caa3c5937d5a3aa5ca3a9a5bcac3bd5a96c3b

请给出一个符合上述列表格式的完整操作序列,使鼠到达 (14,14),且重排操作总数不超过 50 次。输出必须包含足以核验每次移动、每次重排的合法性以及最终到达出口的信息。

加分任务

另有一个 10×10 迷宫:

text
63aaac95c57baca9eadcc6c575ed9a5c57eaa96395975533c65c66a95c979566abae9ac5bbc7b7a6ec9e3eab563659c5737a

可以额外提交一个从 (0,0)(9,9) 的解,要求重排次数不超过 20 次,并且除最后一次鼠的移动外,鼠始终停留在同一坐标。答案仍使用上述列表格式。

出题人:xiue