AcWing-108-奇数码问题

问题

你一定玩过八数码游戏，它实际上是在一个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的网格中进行，其中nn为奇数，1个空格和1~$n^2−1$这$n^2−1$个数恰好不重不漏地分布在n×n的网格中。

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

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

输入格式

多组数据，对于每组数据：

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

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

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

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

题解

#include<iostream>
#include<cstdio>

using namespace std;

const int MAX = 3e5;

int a[MAX];
int back[MAX];
long long cnt;

void merge(int l, int r, int mid) {
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) back[k++] = a[i++];
        else {
            back[k++] = a[j++];
            cnt += mid - i + 1;
        }
    }
    while (i <= mid) back[k++] = a[i++];
    while (j <= r) back[k++] = a[j++];

    for (int k = l; k <= r; ++k) a[k] = back[k];
}

void merge_sort(int l, int r) {
    if (l >= r) return;
    if (l + 1 == r) {
        if (a[l] > a[r]) {
            swap(a[l], a[r]);
            cnt++;
        }
        return;
    }

    int mid = (l + r) / 2;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    merge(l, r, mid);
}

int main() {
    int n;
    while (cin >> n) {
        cnt = 0;
        int k = 1;
        for (int i = 0; i < n * n; ++i) {
            scanf("%d", &a[k]);
            if (a[k] != 0) k++;
        }
        merge_sort(1, k);
        long long cnt1 = cnt;
        cnt = 0;

        k = 1;
        for (int i = 0; i < n * n; ++i) {
            scanf("%d", &a[k]);
            if (a[k] != 0) k++;
        }
        merge_sort(1, k);

        if ((cnt1 & 1) ^ (cnt & 1)) cout << "NIE" << endl;
        else cout << "TAK" << endl;
    }

    return 0;
}