奇数码问题

你一定玩过八数码游戏,它实际上是在一个3 × 3的网格中进行的,1个空格和1 ~ 8这8个数字恰好不重不漏地分布在这3 × 3的网格中。
例如:
5 2 8
1 3
4 6 7

在游戏过程中,可以把空格与其上、下、左、右四个方向之一的数字交换(如果存在)。
例如在上例中,空格可与左、上、下面的数字交换,分别变成:
5 2 8
1 3
4 6 7

5 2
1 3 8
4 6 7

5 2 8
1 3 7
4 6

奇数码游戏是它的一个扩展,在一个n × n的网格中进行,其中n为奇数,1个空格和1 ~ n × n - 1这n × n - 1个数恰好不重不漏地分布在n × n的网格中。
空格移动的规则与八数码游戏相同,实际上,八数码就是一个n=3的奇数码游戏。

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

输入
多组数据,对于每组数据:
第1行一个整数n,n<500,n为奇数。
接下来n行每行n个整数,表示第一个局面。
接下来n行每行n个整数,表示第二个局面。
局面中每个整数都是0~n*n-1之一,其中用0代表空格,其余数值与奇数码游戏中的意义相同,保证这些整数的分布不重不漏。

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

输入样例:

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

输出样例:
TAK
TAK

题解:
奇数码性质 + 归并排序

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

#define lowbit(x) x & (-x)
#define lson left,mid,root << 1
#define rson mid+1,right,root << 1 | 1

using namespace std;

typedef pair<int, int> PII;
typedef long long ll;
typedef unsigned long long ull;
const ll mod=1e9+7;
const ll inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-8;
const int maxn=1e5+100;

int a[250005];
int b[250005];
int temp[250005];

ll mergesort(int a[], int l, int r)
{
    if(l >= r)
        return 0;

    ll cnt = 0;

    int mid = l + r >> 1;
    cnt += mergesort(a, l, mid);
    cnt += mergesort(a, mid + 1, r);

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


    return cnt;
}

int main()
{
    int n;
    while(scanf("%d",&n) != EOF)
        {
        int x;
        int num = 0;
        for(int i = 1; i <= n * n; i ++)    
            {
                scanf("%d",&x);
                if(x)
                    a[++ num] = x;
            }

        num = 0;
        for(int i = 1; i <= n * n; i ++)
            {
                scanf("%d",&x);
                if(x)
                    b[++ num] = x;
            }


        ll cnta = mergesort(a, 1, n * n - 1);   
        ll cntb = mergesort(b, 1, n * n - 1);

        if((cnta & 1) == (cntb & 1))
            puts("TAK");
        else
            puts("NIE");
        }
    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注