..
AcWing 108. 奇数码问题
奇数码问题游戏两个局面可达，当且仅当两个局面下网格中的数依次写成 $1$ 行 $n * n - 1$ 个元素的序列后（不考虑空格），逆序对个数的奇偶行相同。
例如题目描述中的第一个局面写成 $[5 2 8 1 3 4 6 7]$。
该结论的必要性很容易证明：
空格左右移动时，写成的序列显然不变；
空格向上（下）移动时，相当于某个数与它后（前）边的 $n - 1$ 个数交换了位置，因为 $n - 1$ 是偶数，所以逆序对数的变化也只能是偶数。
上面的结论还可以扩展到 $n$ 为偶数的情况，这两个局面可达，当且仅当两个局面对应网格写成序列后，“逆序对数之差” 和 “两个局面下空格所在的行数之差” 奇偶性相同。
事实上，在 $n * m$ 网格上 $(n, m \geq 2)$ 也服从上述两个结论之一（根据列数奇偶性分情况讨论）。
总而言之，$n * m$ 数码问题的有解性判定，可以转化为归并排序求逆序对来解决。
完整代码：奇数码问题.cpp