Eight Puzzle 可解性判定

题目描述

$Eight Puzzle$ 与其他滑动图块谜题一起，是人工智能中著名的问题之一。它与国际象棋、井字棋和西洋双陆棋一起被用于研究搜索算法。

$8$ 个谜题可以概括为 $M × N$ 谜题，其中 $M$ 和 $N$ 中至少有一个是奇数。该拼图由 $MN − 1$ 个滑动图块构成，每个图块上都有一个从 $1$ 到 $MN − 1$ 的数字，装在一个 $M x N$ 框架中，缺少一个图块。例如，当 $M = 4$ 且 $N = 3$ 时，拼图可能如下所示：

$1$ $6$ $2$
$4$ $0$ $3$
$7$ $5$ $9$

$10$ $8$ $11$

我们将缺失的瓦片称为 $0$。唯一合法的作是交换 $0$ 和与其共享一条边的瓦片。该拼图的目标是找到一系列合法作，使其看起来像：

$1$ $2$ $3$
$4$ $5$ $6$
$7$ $8$ $9$
$10$ $11$ $0$

输入输出格式

输入格式

输入由多个测试用例组成。每个测试用例都以包含 $M$ 和 $N$ $(2 ≤ M, N ≤ 999)$ 的行开头。这一行后面是 $M$ 行，包含 $N$ 个数字，每个数字描述一个 $M × N$ 个谜题。

输出格式

为每个测试用例输出一行，如果可以解决难题，则包含一个单词 $YES$，否则为 $NO$。

示例

输入样例

3 3
1 0 3
4 2 5
7 8 6
4 3
1 2 5
4 6 9
11 8 10
3 7 0
0 0

输出样例

YES
NO

题目来源

$POJ$ 月刊--$2006.07.30$， $newton88518$