题目描述

你一定玩过八数码游戏，它实际上是在一个 3×3 的网格中进行的，1 个空格和 1∼8 这 8 个数字恰好不重不漏地分布在这 3×3 的网格中。

例如：

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×n 的网格中进行，其中 n 为奇数，1 个空格和 1∼n2−1 这 n2−1 个数恰好不重不漏地分布在 n×n 的网格中。

空格移动的规则与八数码游戏相同，实际上，八数码就是一个 n=3 的奇数码游戏。

现在给定两个奇数码游戏的局面，请判断是否存在一种移动空格的方式，使得其中一个局面可以变化到另一个局面。

输入格式
多组数据，对于每组数据：

第 1 行输入一个整数 n，n 为奇数。

接下来 n 行每行 n 个整数，表示第一个局面。

再接下来 n 行每行 n 个整数，表示第二个局面。

局面中每个整数都是 0∼n2−1 之一，其中用 0 代表空格，其余数值与奇数码游戏中的意义相同，保证这些整数的分布不重不漏。

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

数据范围
1≤n<500

样例

输入样例：
3
1 2 3
0 4 6
7 5 8
1 2 3
4 5 6
7 8 0
1
0
0
输出样例：
TAK
TAK

算法1 归并排序+算逆序对数

两个局面可达，则它们的逆序对数奇偶性一致
左右交换两个数，状态的序列不会改变（空格用0来表示，但不会存储在序列中）
上下交换两个数，等同于将某个数与前后n-1个数交换
假设原始局面序列的逆序对数是奇数。某个数i要与后面的的n-1个数交换，i要么比后面的n-1个数大偶数个，要么大奇数个。因为n-1为偶数，若是i比后面的n-1个数大偶数个，则i比后面的n-1个数小偶数个；若是i比后面的n-1个数大奇数个，则i比后面的n-1个数小奇数个。同里i与前面的n-1个数交换也是一样的。
也就是说不管原始序列怎么交换数字，逆序对数的变换都是偶数（奇数-奇数=偶数 偶数-偶数=偶数）
若初始的逆序对数是偶数，偶数+-变化的逆序对数（偶数）=偶数
若初始的逆序对数是奇数，奇数+-变化的逆序对数（偶数）=奇数
所以我们可以通过比较两个转态的逆序对数的奇偶是否相同即可判断是否可达

时间复杂度

归并排序的时间复杂度nlogn
在归并两个子区间并计算逆序对的个数时，最多计算n/2次
所以时间复杂杂度为O（n^2logn）

参考文献

C++ 代码

#include<iostream>
using namespace std;
const int N = 2.5e5 + 5;//数字个数不会超过2.5e5(n<500)
int state1[N], state2[N];//保存当前的两个局面
int temp[N];//归并两端子区间时用到的临时变量
int cnt1, cnt2;//记录两个状态的逆序对数，此题的最大逆序数理论上会报int(最大到10^10的数量级)，但实际不会
               //因为这题其实并不关心逆序对数是多少，我们可以在每次归并完两个子区间后，把累计的逆序数mod2


void merge(int arry[],int left, int right) {//对状态数进行归并排序，在此过程中统计出逆序对数
    if (left == right) return;              //过程就是传统的归并排序模式
    int mid = left + ((right - left) >> 1);
    merge(arry,left, mid);
    merge(arry, mid + 1, right);
    int t = 0;
    {
        int i = left, j = mid + 1;
        while (i <= mid && j <= right) {
            if (arry[i] <= arry[j]) temp[t++]=arry[i++];
            else {//如果右区间当前的数小于左区间当前的数，那么左区间后面的数都比右区间当前的数大
                cnt1 += mid - i + 1;//此时的逆序对数，就是左区间的长度
                temp[t++] = arry[j++];
            }
        }
        cnt1%=2;cnt2%=2;
        while (i <= mid) temp[t++] = arry[i++];
        while (j <= right) temp[t++] = arry[j++];
    }
    for (int i = left; i <=right; ++i) arry[i] = temp[i-left];
}


bool reachable(int end) {
    merge(state1, 1, end);//算出局面一的逆序数
    merge(state2, 1, end);//算出局面二的逆序数
    if ((cnt1 & 1 && cnt2 & 1)||(cnt1%2==0&&cnt2%2==0)) return 1;//两局面逆序数同为奇数或偶数则互相可达
    return 0;
}


int main() {
    int n;
    while (cin >> n) {
        int end = n * n, v;
        for (int i = 1,t=1; i <= end; ++i) {
            scanf("%d", &v);
            if (v) state1[t++] = v;//若输入的不是0则记录数据，t用来统计下个数据因输入的位置
        }
        for (int j = 1,t=1; j <= end; ++j) {
            scanf("%d", &v);
            if (v) state2[t++] = v;
        }
        if (n == 1) printf("TAK\n");//n为1就不用算了
        else if (reachable(end-1)) printf("TAK\n");
        else printf("NIE\n");
        cnt1=cnt2=0;//进行下一轮的计算，将逆序对数重置
    }
}