这是一个经典的问题，用逆序数的奇偶性来判断数字拼图游戏的解的存在性

思路：

5 2 8
1 3 _
4 6 7
将这个样例写成一维数组{5，2，8，1，3，4，6，7}的形式后可以发现，当空格左右移动时，每个数字的相对顺序不变，当空格上下移动时，相当于将某个数与前/后n-1个数交换位置。因为n为奇数，所以n-1为偶数，相当对序列进行偶数次交换，序列逆序对的奇偶性不变，所以我们只需考虑原始情况逆序对奇偶性与目标情况逆序对奇偶性是否相同即可
（逆序数判断数字拼图游戏的解的存在性的定理网络上可以找到详细证明过程）

code：

#include <iostream>
#include <cstdio>
#include <iomanip>
#include <cstring>
#include <string>
#include <cmath>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <algorithm>
#include <functional>
typedef long long ll;
using namespace std;
const int N = 300005;
int q[N], t[N];
ll ans = 0;
void merge_sort(int q[], int l, int r)
{
    if (l >= r)
        return; //当没有元素或者只有一个元素时，无需排序，直接退出。

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r); //分治，区间一分为二。

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r) //子序列排序（合并）。每个子序列内部其实都是有序的，
                               //因为把序列分解到一个元素时。无需排序，而在合并的过程中，合并成的子序列又是有序的，
                               //所以每个子序列内部是有序的。例：（a[1,3],b[2,9]--->c[1,2,3,9]）每个子序列内部都有序。
        if (q[i] <= q[j])
            t[k++] = q[i++];
        else
        {
            ans += mid - i + 1;
            t[k++] = q[j++];
        }
    while (i <= mid)
        t[k++] = q[i++];
    while (j <= r)
        t[k++] = q[j++];

    for (i = l, j = 0; i <= r; i++, j++)
        q[i] = t[j]; //归并
}

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifdef ak
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int n;
    while (cin >> n)
    {
        int t, pos = 0;
        ans = 0;
        for (int i = 0; i < n * n; i++)
        {
            cin >> t;
            if (t)
            {
                q[pos] = t;
                pos++;
            }
        }
        ll sum1, sum2;
        merge_sort(q, 0, n * n - 1);
        sum1 = ans;
        ans = 0;
        pos = 0;
        for (int i = 0; i < n * n; i++)
        {
            cin >> t;
            if (t)
            {
                q[pos] = t;
                pos++;
            }
        }
        merge_sort(q, 0, n * n - 1);
        sum2 = ans;
        if (sum1 % 2 == sum2 % 2)
        {
            cout << "TAK" << endl;
        }
        else
        {
            cout << "NIE" << endl;
        }
    }
    return 0;
}