题目链接：题目链接
Just an Old Puzzle
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 2749 Accepted Submission(s): 875

Problem Description
You are given a 4 × 4 grid, which consists of 15 number cells and an empty cell.
All numbers are unique and ranged from 1 to 15.
In this board, the cells which are adjacent with the empty cell can move to the empty cell.
Your task is to make the input grid to the target grid shown in the figure below.
In the following example (sample input), you can get the target grid in two moves.

Input
The first line contains an integer T (1 <= T <= 10^5) denoting the number of test cases.
Each test case consists of four lines each containing four space-separated integers, denoting the input grid. 0 indicates the empty cell.

Output
For each test case, you have to print the answer in one line.
If you can’t get the target grid within 120 moves, then print ‘No’, else print ‘Yes’.

Sample Input
2
1 2 3 4
5 6 7 8
9 10 0 12
13 14 11 15
1 2 3 4
5 6 7 8
9 10 11 12
13 15 14 0

Sample Output
Yes
No
题意：给出一个4x4网格，有一个空格子，目标顺序是按顺序1-15排列最后一个是空格子，给出初始排列问你120步内是否必然有解
考查：逆序数、数学华容道
思路：赛中看到这题首先想到搜索，但是4x4网格的情况太多，搜到120步估计也T了，尝试找规律，但是很难统一找出解的规律，后来看了一眼代码十分简短，我知道必然是有什么性质，下面我们进行讨论。
首先，本题是经典的数学华容道问题。前置知识：逆序数
①逆序数，即一个数字序列，将其中所有数字依次两两对比，若大数在前，小数在后，那么这就是一对逆序数。这里说到的逆序数，指的是数字序列中逆序数对的数量。比如序列1、2、3、4、5、6、8、7，逆序数是1，即8和7。序列1、2、3、4、5、9、8、7，逆序数是3，即9和8、9和7、8和7。
②有解的前提，当且仅当满足下列条件之一：
1、若格子列数为奇数，则逆序数必须为偶数；
2、若格子列数为偶数，且逆序数为偶数，则当前空格所在行数与初始空格所在行数的差为偶数；
3、若格子列数为偶数，且逆序数为奇数，则当前空格所在行数与初始空格所在行数的差为奇数。
其正确性的推导涉及数学证明

本题也可以看作是奇数码问题的拓展（如上图）：
奇数码问题及拓展
作者：寻找&星空の孩子
参考一个对奇数码问题及其拓展NN数码问题的讨论。
我们发现本题是否有解和排列的逆序数相关，转换一维数组后求逆序数和空格位置即可，至于步数限制，十五数码问题在80步内必然有解，八数码问题在31步内必然有解-证明参考：维基百科
我发现在证明中提到A搜索算法求最优解，所以本题应该也可以通过搜索来解决，等我学会了就研究一下，本题的最简单方法还是利用刚刚的性质。
AC代码：

#include <bits/stdc++.h>

#define rep(i, n) for(int i=1;i<=n;i++)
#define per(i, n) for(int i=n;i>=1;i--)
#define pb(x) push_back(x)
using namespace std;
typedef long long ll;
const int maxn =50;
//const ll inf = INT64_MAX;
using namespace std;
int a[maxn];
int kong,num;

int main() {
    int n, T;
    scanf("%d", &T);
    while (T--) {
        kong=0,num=0;
        rep(i,16){
            scanf("%d",&a[i]);
            if(a[i]==0) {//记录空格行数
                kong=i/4;
                if(i%4!=0) kong++;
            }
            else{
                rep(j,i-1){
                    if(a[j]==0) continue;
                    if(a[j]>a[i]) num++;
                }
            }
        }
        if((4-kong)%2==num%2)//对应有解的第二、三种情况
            //因为我们发现 只要当前空格所在行数与初始空格所在行数的差 和 逆序数 奇偶性相同就是有解的
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
    return 0;
}