POJ 2893 M × N Puzzle——八数码有解条件

概述题意：给定M*N的数码图，问能否移动到最终状态 分析 有解的判定条件可见 八数码有解条件 值得一提的是，这道题求逆序对卡树状数组，只能用归并排序。 #include<cstdio>#include<algorithm>#include<cstring>using namespace std;const int maxn = 1e6 + 10;int n,m,pos,x,an

题意：给定M*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)  //对seq进行排序{    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;  //ans就是逆序对个数    }    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;}

 

 

参考链接：https://www.cnblogs.com/nopartyfoucaodong/p/9673434.html

总结

以上是内存溢出为你收集整理的POJ 2893 M × N Puzzle——八数码有解条件全部内容，希望文章能够帮你解决POJ 2893 M × N Puzzle——八数码有解条件所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。