{"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\"\u003e15数码难题已经存在了100多年;即使你不知道它的名字,你也见过它。它由15个滑动方块构成,每个方块上都有一个从1到15的数字,并且全部放在一个4x4的框架中,其中有一个方块缺失。让我们把缺失的方块称为\u0027x\u0027;这个难题的目标是排列方块,使它们按照以下顺序排列:\u003cbr\u003e\u003cpre\u003e\u003cbr\u003e 1 2 3 4\u003cbr\u003e 5 6 7 8\u003cbr\u003e 9 10 11 12\u003cbr\u003e13 14 15 x\u003cbr\u003e\u003c/pre\u003e\u003cbr\u003e唯一的合法操作是将\u0027x\u0027与其共享边的一个方块交换位置。例如,以下移动序列解决了一个稍微打乱的难题:\u003cbr\u003e\u003cpre\u003e\u003cbr\u003e 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4\u003cbr\u003e 5 6 7 8 5 6 7 8 5 6 7 8 5 6 7 8\u003cbr\u003e 9 x 10 12 9 10 x 12 9 10 11 12 9 10 11 12\u003cbr\u003e13 14 11 15 13 14 11 15 13 14 x 15 13 14 15 x\u003cbr\u003e r-\u0026gt; d-\u0026gt; r-\u0026gt;\u003cbr\u003e\u003c/pre\u003e\u003cbr\u003e上一行中的字母表示\u0027x\u0027方块与其邻居在每一步中交换的方块;合法值为\u0027r\u0027,\u0027l\u0027,\u0027u\u0027和\u0027d\u0027,分别表示右、左、上和下。 \u003cbr\u003e\u003cbr\u003e并非所有的难题都能够解决;1870年,一个名叫Sam Loyd的人因分发一个无解版本的难题而出名,让许多人感到沮丧。事实上,要使一个常规难题变成一个无解难题,你只需要交换两个方块(当然不包括缺失的\u0027x\u0027方块)。\u003cbr\u003e\u003cbr\u003e在这个问题中,你将编写一个解决较不为人知的8数码难题的程序,由三行三列的方块组成。\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"你将会收到几个8数码难题配置的描述。一个描述就是方块的初始位置列表,行从上到下列出,每行中从左到右列出方块,其中方块用数字1到8表示,另外还有\u0027x\u0027。例如,这个难题 \u003cbr\u003e\u003cbr\u003e 1 2 3 \u003cbr\u003e x 4 6 \u003cbr\u003e 7 5 8 \u003cbr\u003e\u003cbr\u003e由这个列表描述:\u003cbr\u003e\u003cbr\u003e1 2 3 x 4 6 7 5 8\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"你将会打印到标准输出,如果难题没有解决方案,则打印单词``unsolvable\u0027\u0027,否则打印一个由字母\u0027r\u0027,\u0027l\u0027,\u0027u\u0027和\u0027d\u0027组成的字符串,描述一系列移动以生成解决方案。字符串不应包含空格,并且应该从行的开头开始。在案例之间不要打印空行。\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 3 4 1 5 x 7 6 8\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eullddrurdllurdruldr\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}