【逆序对】【cofun1917】奇数码问题

【cofun1917】奇数码问题

Description
你一定玩过八数码游戏，它实际上是在一个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 _
奇数码游戏是它的一个扩展，在一个nn的网格中进行，其中n为奇数，1个空格和1~nn-1这nn-1个数恰好不重不漏地分布在nn的网格中。
空格移动的规则与八数码游戏相同，实际上，八数码就是一个n=3的奇数码游戏。
现在给定两个奇数码游戏的局面，请判断是否存在一种移动空格的方式，使得其中一个局面可以变化到另一个局面。

Input Format
多组数据，对于每组数据：
第1行一个奇整数n。
接下来n行每行n个整数，表示第一个局面。
接下来n行每行n个整数，表示第二个局面。
局面中每个整数都是0~n*n-1之一，其中用0代表空格，其余数值与奇数码游戏中的意义相同，保证这些整数的分布不重不漏。
Output Format
对于每组数据，若两个局面可达，输出TAK，否则输出NIE。

Sample Input
3
1 2 3
0 4 6
7 5 8
1 2 3
4 5 6
7 8 0
1
0
0
Sample Output
TAK
TAK

Hint
数据范围与约定
对于30%的数据，1<=n<=3；
对于60%的数据，1<=n<=50；
对于100%的数据，1<=n<=500，n为奇数，每个测试点不超过10组。

---

• 分析：
  
  1. 二维奇数码问题性质：
     把矩阵中的所有数依次排成一行，求逆序对数。如果N为奇数，那么上下移动，左右移动都不会改变序列的逆序值的奇偶性，若起始状态逆序对数与目标状态同奇偶，则可达，否则不可达。
  2. 二维偶数码&三维性质拓展
  3. 问题转化为求逆序对。

---

• 代码：

#include<bits/stdc++.h>
 using namespace std;

 int n, i, j, x, s1, s2, c[250005];

 inline int read()
 {
    int x = 0, w = 1;
    char ch = 0;
    while(ch < '0' || ch > '9')
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
     }
    while(ch >= '0' && ch <= '9')
          x = x * 10 + ch - '0', ch = getchar();
    return x * w;
 } //读入优化

 inline int lowbit(int x)
 {
    return x & (-x);
 }

 inline int work(int x)
 {
    int s = 0;
    for(; x; x -= lowbit(x)) s += c[x];
    return s;
 }

 inline void add(int x)
 {
    for(; x < n; x += lowbit(x)) c[x] ++;
 }

 int main()
 {

    while(~ scanf("%d", &n))
    {
        n *= n;
        memset(c, 0, sizeof(c));
        for(i = j = 1, s1= 0; i <= n; ++ i)
        {
            x = read();
            if (x) {s1 += j - work(x); add(x); j ++;};
        }
        memset(c, 0, sizeof(c));
        for(i = j = 1, s2 = 0; i <= n; ++ i)
        {
            x = read();
            if (x) {s2 += j - work(x); add(x); j ++;};
        }
        if ((s1 & 1) == (s2 & 1)) printf("TAK\n");else printf("NIE\n");
    }

    return 0;

 }