链接：https://ac.nowcoder.com/acm/contest/1001/F
来源：牛客网

题目描述
你一定玩过八数码游戏，它实际上是在一个33的网格中进行的，1个空格和1~8这8个数字恰好不重不漏地分布在这33的网格中。
例如：
5 2 8
1 3 _
4 6 7
在游戏过程中，可以把空格与其上、下、左、右四个方向之一的数字交换（如果存在）。
例如在上例中，空格可与左、上、下面的数字交换，分别变成：
5 2 8 5 2 _ 5 2 8
1 _ 3 1 3 8 1 3 7
4 6 7 4 6 7 4 6 _

奇数码游戏是它的一个扩展，在一个n\times nn×n的网格中进行，其中n为奇数，1个空格和1\sim n\times n-11∼n×n−1这n\times n-1n×n−1个数恰好不重不漏地分布在n*n的网格中。
空格移动的规则与八数码游戏相同，实际上，八数码就是一个n=3的奇数码游戏。
现在给定两个奇数码游戏的局面，请判断是否存在一种移动空格的方式，使得其中一个局面可以变化到另一个局面。

输入描述:

多组数据，对于每组数据：
第1行一个整数n，n \lt 500n<500，n为奇数。
接下来n行每行n个整数，表示第一个局面。
接下来n行每行n个整数，表示第二个局面。
局面中每个整数都是0\sim n\times n-10∼n×n−1之一，其中用0代表空格，其余数值与奇数码游戏中的意义相同，保证这些整数的分布不重不漏。

输出描述:

对于每组数据，若两个局面可达，输出TAK，否则输出NIE。

示例1
输入

3
1 2 3
0 4 6
7 5 8
1 2 3
4 5 6
7 8 0
1
0
0

输出

TAK
TAK

思路：
本题用归并排序求解。本题是一道经典的逆序对求解问题，奇数码0交换位置后除零外的序列逆序对的奇偶性是不变的，所以只需对比两个逆序对的奇偶性是否一致即可求解。

#include<bits/stdc++.h>
using namespace std;
const int mai=250005;
typedef long long ll;
ll a[mai],b[mai],cnt=0;
void merge(ll l,ll mid,ll r){
    ll i=l,j=mid+1,t=0;
    while(i<=mid&&j<=r){
        if(a[i]>a[j]){
            b[t++]=a[j++];
            cnt+=mid-i+1;
        }
        else b[t++]=a[i++];
    }
    while(i<=mid) b[t++]=a[i++];
    while(j<=r) b[t++]=a[j++];
    for(int i=0;i<t;i++) a[l+i]=b[i];
}
void mergesort(ll l,ll r){
    if(l<r){
        ll mid=(l+r)/2;
        mergesort(l,mid);
        mergesort(mid+1,r);
        merge(l,mid,r);
    }
}

int main(){
    ll n,sum0,sum1;
    while(scanf("%lld",&n)!=EOF){
        cnt=0;
        int kp=0;
        for(ll i=0;i<n*n;i++){
        ll f;
        scanf("%lld",&f);
        if(f!=0)
            a[kp++]=f;
        }
        mergesort(0,n*n-1);
        sum0=cnt;
        cnt=0;
        kp=0;
        for(ll i=0;i<n*n;i++){
        ll f;
        scanf("%lld",&f);
        if(f!=0)
            a[kp++]=f;
        }
        mergesort(0,n*n-1);
        sum1=cnt;
        if((sum0%2)==(sum1%2))
            cout<<"TAK"<<endl;
        else cout<<"NIE"<<endl;
    }
}