P10454 奇数码问题-平芜编程栈

P10454 奇数码问题

题目描述

你一定玩过八数码游戏，它实际上是在一个3×33 \times 33×3的网格中进行的，111个空格和1∼81 \sim 81∼8这888个数字恰好不重不漏地分布在这3×33 \times 33×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×nn \times nn×n的网格中进行，其中nnn为奇数，111个空格和1∼n2−11 \sim n^2-11∼n2−1这n2−1n^2-1n2−1个数恰好不重不漏地分布在n×nn \times nn×n的网格中。

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

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

输入格式

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

第111行输入一个整数nnn，nnn为奇数。

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

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

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

TAK TAK

说明/提示

1≤n<5001 \le n < 5001≤n<500

奇数码问题题解

这是我针对奇数码问题的解题题解，核心依托归并排序求逆序对来完成可达性判断，下面结合我的代码详细拆解解题思路。

一、题目分析

本题要求我们判断两个n×nn \times nn×n（nnn为奇数）的奇数码局面是否可达，其中000代表空格，其余数字为1∼n2−11 \sim n^2-11∼n2−1，空格仅能与上下左右相邻数字交换。这是一道经典的数码问题，核心在于掌握奇数码局面可达性的判定定理，同时需要高效求解逆序对。

二、核心解题思路

1. 奇数码可达性判定定理

对于nnn为奇数的奇数码问题，两个局面可达的充要条件是：忽略空格（数字000）后，两个局面的数字序列的逆序对数量奇偶性相同。

逆序对定义：对于一个数字序列，若存在两个数aia_iai和aja_jaj（i<ji < ji<j），满足ai>aja_i > a_jai>aj，则称这对数字为一个逆序对。
为什么该定理成立？因为空格的移动（与相邻数字交换）不会改变整个序列逆序对数量的奇偶性，因此只有当两个局面的逆序对奇偶性一致时，才可以通过移动空格实现相互转化。

2. 逆序对的高效求解

由于nnn最大接近500500500，n2n^2n2最大为250000250000250000，普通的暴力枚举（O(n4)O(n^4)O(n4)）会超时，因此我采用归并排序求解逆序对，时间复杂度为O(mlog⁡m)O(m \log m)O(mlogm)（m=n2m = n^2m=n2），能够高效处理最大数据量。

三、代码逐部分解析

intn;inta[250005];intt[250005];longlongans,ans1,ans2;voidms(intl,intr){if(l==r)return;// 递归终止条件：区间仅含一个元素，无需排序intm=(l+r)/2;ms(l,m);// 递归处理左区间 [l, m]ms(m+1,r);// 递归处理右区间 [m+1, r]intlp=l;// 左区间指针intrp=m+1;// 右区间指针inttp=l;// 临时数组t的指针while(lp<=m&&rp<=r){if(a[rp]<a[lp]){t[tp]=a[rp];if(a[rp]!=0){// 忽略空格0，不统计0参与的逆序对ans+=m-lp+1;// 核心：统计逆序对数量}tp++;rp++;}else{t[tp]=a[lp];tp++;lp++;}}// 处理左区间剩余元素while(lp<=m){t[tp]=a[lp];tp++;lp++;}// 处理右区间剩余元素while(rp<=r){t[tp]=a[rp];tp++;rp++;}// 将临时数组的有序元素复制回原数组afor(inti=l;i<=r;i++){a[i]=t[i];}return;}longlongcalc(intx){for(inti=1;i<=x*x;i++){cin>>a[i];// 读取x*x个元素，将二维矩阵展平为一维数组}ans=0;// 初始化逆序对数量为0ms(1,x*x);// 调用归并排序统计逆序对returnans;// 返回当前局面的逆序对数量}intmain(){while(cin>>n){// 多组输入，直到输入结束ans1=calc(n);// 计算第一个局面的逆序对数量ans2=calc(n);// 计算第二个局面的逆序对数量if(ans1%2==ans2%2){cout<<"TAK\n";// 奇偶性相同，可达}else{cout<<"NIE\n";// 奇偶性不同，不可达}}return0;}

1. 全局变量说明

nnn：存储奇数码矩阵的边长，因多组输入，在循环中读取。
a[]a[]a[]：用于存储展平后的n×nn \times nn×n数码矩阵（二维转一维，方便归并排序处理），数组大小250005250005250005是为了容纳500×500=250000500 \times 500 = 250000500×500=250000个元素，预留充足余量。
t[]t[]t[]：归并排序的临时辅助数组，用于合并两个有序子数组，避免直接修改原数组导致数据混乱。
ansansans：临时存储单个局面的逆序对数量；ans1ans1ans1、ans2ans2ans2分别存储两个输入局面的逆序对数量。

2. 归并排序求逆序对（ms 函数）

函数功能：对aaa数组的[l,r][l, r][l,r]区间进行归并排序，同时统计该区间内忽略000后的逆序对数量，累加到全局变量ansansans中。
核心逻辑（合并阶段统计逆序对）：当a[rp]<a[lp]a[rp] < a[lp]a[rp]<a[lp]时，说明a[rp]a[rp]a[rp]与左区间中从lplplp到mmm的所有元素都构成逆序对，因此逆序对数量增加m−lp+1m - lp + 1m−lp+1；同时通过a[rp]!=0判断，跳过空格000，不统计其参与的逆序对，符合可达性判定定理的要求。
归并排序的稳定性：保证了在统计逆序对时不会重复或遗漏，是高效求解逆序对的经典方法。