{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e八数码问题,也称为“九宫格”,源自一个古老的游戏。\u003cbr\u003e\u003cbr\u003e在这个游戏中,给定一个3x3的棋盘和8个方块。这些方块编号从1到8,每个方块覆盖一个格子。如你所见,有一个空格可以用 \u0027X\u0027 表示。与空格有公共边的格子中的方块可以移动到空格中。这个操作会导致 \u0027X\u0027 与一个方块交换位置。\u003cbr\u003e\u003cbr\u003e我们用符号 \u0027r\u0027 表示将 \u0027X\u0027 与其右侧的方块交换位置,\u0027l\u0027 表示左侧,\u0027u\u0027 表示上侧,\u0027d\u0027 表示下侧。\u003cbr\u003e\u003cbr\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/671f4d3b6e4f813711be59c11286128e?v\u003d1712822518\"\u003e\u003cbr\u003e\u003cbr\u003e棋盘的状态可以用字符串 S 表示,遵循以下规则。\u003cbr\u003e\u003cbr\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/23e43083209c3a766ab92e1429ae5a49?v\u003d1712822518\"\u003e\u003cbr\u003e\u003cbr\u003e问题是要通过一系列 \u0027r\u0027、\u0027u\u0027、\u0027l\u0027、\u0027d\u0027 操作将棋盘从状态 A 转换到状态 B。要求找到符合以下条件的结果:\u003cbr\u003e1. 在所有可能解中,它的长度最短。\u003cbr\u003e2. 在所有长度最短的解中,它是字典序最小的一个。\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"第一行是 T (T \u0026lt;\u003d 200),表示此问题的测试用例数量。\u003cbr\u003e\u003cbr\u003e每个测试用例的输入由两行组成,第一行是状态 A,第二行是状态 B。\u003cbr\u003e保证从状态 A 到 B 有可行解。\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,期望输出两行。\u003cbr\u003e\u003cbr\u003e第一行格式为 \"Case x: d\",其中 x 是从一开始计数的案例编号,d 是将 A 转换为 B 需要的操作列表的最小长度。\u003cbr\u003eS 是符合条件的操作列表,应显示在第二行。\u003cbr\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n12X453786\r\n12345678X\r\n564178X23\r\n7568X4123\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 2\r\ndd\r\nCase 2: 8\r\nurrulldr\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}