链接: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; } }