{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003e八数码问题(Eight Puzzle)是人工智能中著名的滑动拼图问题之一。与国际象棋、井字棋和西洋双陆棋一样,它被用来研究搜索算法。\u003c/p\u003e\u003cp\u003e八数码问题可以推广为一个 \u003ci\u003eM\u003c/i\u003e × \u003ci\u003eN\u003c/i\u003e 拼图,其中至少一个 \u003ci\u003eM\u003c/i\u003e 和 \u003ci\u003eN\u003c/i\u003e 是奇数。这个拼图由 \u003ci\u003eMN\u003c/i\u003e − 1 个滑动块组成,每个块上都有一个从1到 \u003ci\u003eMN\u003c/i\u003e − 1 的数字,这些块被放入一个 \u003ci\u003eM\u003c/i\u003e 行 \u003ci\u003eN\u003c/i\u003e 列的框架中,其中有一个块缺失。例如,当 \u003ci\u003eM\u003c/i\u003e \u003d 4 且 \u003ci\u003eN\u003c/i\u003e \u003d 3 时,一个拼图可能如下所示:\u003c/p\u003e\u003cdiv align\u003d\"center\"\u003e\u003ctable border\u003d\"1\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e1\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e6\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e2\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e4\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e0\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e3\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e7\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e5\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e9\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e10\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e8\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e11\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/div\u003e\u003cp\u003e让我们将缺失的块称为0。唯一的合法操作是交换0和与其共享边的块。拼图的目标是找到一系列合法操作,使其看起来像这样:\u003c/p\u003e\u003cdiv align\u003d\"center\"\u003e\u003ctable border\u003d\"1\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e1\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e2\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e3\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e4\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e5\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e6\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e7\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e8\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e9\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e10\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e11\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e0\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/div\u003e\u003cp\u003e以下步骤解决了上面给出的拼图。\u003c/p\u003e\u003cdiv align\u003d\"center\"\u003e\u003ctable border\u003d\"0\" width\u003d\"600\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd align\u003d\"center\"\u003e\u003cp align\u003d\"center\"\u003e开始\u003c/p\u003e\u003c/td\u003e\u003ctd width\u003d\"15%\" align\u003d\"center\"\u003e\u003cdiv align\u003d\"center\"\u003e\u003ctable border\u003d\"1\" id\u003d\"table1\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e1\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e6\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e2\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e4\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e0\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e3\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e7\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e5\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e9\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e10\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e8\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e11\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/div\u003e\u003c/td\u003e\u003ctd align\u003d\"center\"\u003e\u003cp align\u003d\"center\"\u003e下移\u003cbr\u003e⇒\u003c/p\u003e\u003c/td\u003e\u003ctd width\u003d\"15%\" align\u003d\"center\"\u003e\u003cdiv align\u003d\"center\"\u003e\u003ctable border\u003d\"1\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e1\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e0\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e2\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e4\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e6\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e3\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e7\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e5\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e9\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e10\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e8\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e11\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/div\u003e\u003c/td\u003e\u003ctd align\u003d\"center\"\u003e左移\u003cbr\u003e⇒\u003c/td\u003e\u003ctd width\u003d\"15%\" align\u003d\"center\"\u003e\u003cdiv align\u003d\"center\"\u003e\u003ctable border\u003d\"1\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e1\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e2\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e0\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e4\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e6\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e3\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e7\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e5\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e9\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e10\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e8\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e11\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/div\u003e\u003c/td\u003e\u003ctd align\u003d\"center\"\u003e\u003cp align\u003d\"center\"\u003e上移\u003cbr\u003e⇒\u003c/p\u003e\u003c/td\u003e\u003ctd width\u003d\"15%\" align\u003d\"center\"\u003e\u003cdiv align\u003d\"center\"\u003e\u003ctable border\u003d\"1\" id\u003d\"table5\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e1\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e2\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e3\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e4\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e6\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e0\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e7\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e5\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e9\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e10\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e8\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e11\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/div\u003e\u003c/td\u003e\u003ctd align\u003d\"center\"\u003e\u003cp align\u003d\"center\"\u003e\u003cspan lang\u003d\"en-us\"\u003e…\u003c/span\u003e\u003c/p\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd height\u003d\"20\" align\u003d\"center\" colspan\u003d\"9\"\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\"\u003e\u003cp align\u003d\"center\"\u003e右移\u003cbr\u003e⇒\u003c/p\u003e\u003c/td\u003e\u003ctd width\u003d\"15%\" align\u003d\"center\"\u003e\u003cdiv align\u003d\"center\"\u003e\u003ctable border\u003d\"1\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e1\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e2\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e3\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e4\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e0\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e6\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e7\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e5\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e9\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e10\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e8\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e11\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/div\u003e\u003c/td\u003e\u003ctd align\u003d\"center\"\u003e\u003cp align\u003d\"center\"\u003e上移\u003cbr\u003e⇒\u003c/p\u003e\u003c/td\u003e\u003ctd width\u003d\"15%\" align\u003d\"center\"\u003e\u003cdiv align\u003d\"center\"\u003e\u003ctable border\u003d\"1\" id\u003d\"table7\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e1\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e2\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e3\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e4\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e5\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e6\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e7\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e0\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e9\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e10\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e8\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e11\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/div\u003e\u003c/td\u003e\u003ctd align\u003d\"center\"\u003e上移\u003cbr\u003e⇒\u003c/td\u003e\u003ctd width\u003d\"15%\" align\u003d\"center\"\u003e\u003cdiv align\u003d\"center\"\u003e\u003ctable border\u003d\"1\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e1\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e2\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e3\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e4\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e5\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e6\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e7\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e8\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e9\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e10\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e0\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e11\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/div\u003e\u003c/td\u003e\u003ctd align\u003d\"center\"\u003e\u003cp align\u003d\"center\"\u003e左移\u003cbr\u003e⇒\u003c/p\u003e\u003c/td\u003e\u003ctd width\u003d\"15%\" align\u003d\"center\"\u003e\u003cdiv align\u003d\"center\"\u003e\u003ctable border\u003d\"1\" id\u003d\"table2\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e1\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e2\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e3\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e4\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e5\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e6\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e7\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e8\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e9\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e10\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e11\u003c/td\u003e\u003ctd align\u003d\"center\" width\u003d\"33%\"\u003e0\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/div\u003e\u003c/td\u003e\u003ctd align\u003d\"center\"\u003e\u003cp align\u003d\"center\"\u003e目标\u003c/p\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/div\u003e\u003cp\u003e给定一个 \u003ci\u003eM\u003c/i\u003e × \u003ci\u003eN\u003c/i\u003e 拼图,您需要确定它是否可以被解决。\u003c/p\u003e\u003c/span\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e输入包含多个测试用例。每个测试用例以包含 \u003ci\u003eM\u003c/i\u003e 和 \u003ci\u003eN\u003c/i\u003e(2 ≤ \u003ci\u003eM\u003c/i\u003e, \u003ci\u003eN\u003c/i\u003e ≤ 999)的一行开始。接下来是 \u003ci\u003eM\u003c/i\u003e 行,每行包含 \u003ci\u003eN\u003c/i\u003e 个数字,描述一个 \u003ci\u003eM\u003c/i\u003e × \u003ci\u003eN\u003c/i\u003e 拼图。\u003c/p\u003e\u003cp\u003e输入以一对零结束,这对零不应被处理。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e对于每个测试用例,输出一行,包含一个单词 \u003ctt\u003eYES\u003c/tt\u003e(如果可以解决拼图)或 \u003ctt\u003eNO\u003c/tt\u003e(如果不能解决拼图)。\u003c/p\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\u003e3 3\r\n1 0 3\r\n4 2 5\r\n7 8 6\r\n4 3\r\n1 2 5\r\n4 6 9\r\n11 8 10\r\n3 7 0\r\n0 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eYES\r\nNO\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}