Eight Puzzle 可解性判定算法分析

题目理解

给定一个 $M \times N$ 的滑动拼图，其中：

• 至少 $M$ 或 $N$ 是奇数
• 包含 $MN-1$ 个编号瓦片和一个空缺位($0$)
• 只能交换 $0$ 与相邻瓦片
• 目标状态为数字按行升序排列，$0$ 在右下角

解题方法

核心思路

判断拼图是否可解基于以下数学性质：

1. 逆序对奇偶性：计算除 $0$ 外数字序列的逆序对数
2. 零位置行数：计算 $0$ 所在行从底部数的行数
3. 可解条件：
   • 当 $N$ 为奇数时：逆序对数必须为偶数
   • 当 $N$ 为偶数时：$(逆序对数 + 零位置行数)$ 必须为偶数

算法实现

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int maxn = 1e6 + 10;
int n,m,pos,x,ans,zero;
int seq[maxn],tmp[maxn];

void msort(int l,int r)  // 归并排序计算逆序对
{
    if(l==r) return ;
    int mid=(l+r)>>1;
    msort(l,mid);
    msort(mid+1,r);
    int i=l,j=mid+1,k=l-1;
    while(i<=mid&&j<=r)
    {
        if(seq[i]<=seq[j])
            tmp[++k]=seq[i],i++;
        else tmp[++k]=seq[j],j++,ans+=mid-i+1;  // 统计逆序对
    }
    while(i<=mid)
        tmp[++k]=seq[i],i++;
    while(j<=r)
        tmp[++k]=seq[j],j++;
    for(int qwq=l;qwq<=r;qwq++)
        seq[qwq]=tmp[qwq];
}

int main()
{
    while(scanf("%d%d",&n,&m)==2 && m)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&x);
                if(x) seq[++pos]=x;  // 存储非零数字
                else zero=n-i;      // 计算零位置行数(从底部数)
            }
        msort(1,pos);  // 计算逆序对
        if(m&1) zero=0;  // 当列数为奇数时忽略零位置
        if((ans+zero)%2==0) printf("YES\n");
        else printf("NO\n");
        ans=0;pos=0;zero=0;  // 重置变量
    }
    return 0;
}