poj2893 MN puzzle （nm数码问题）

女爷i 2021-10-18 11:32 268阅读 0赞

## 题意：8数码问题的升级，就是通过移动空格（用0代替）使得原来状态变成有序的1234......0，不过，这题是N\*M数码。 ##

## 分析：考虑终态，实际就是逆序数为0的状态，然后四种操作方式分为：左右移动，对原序列的逆序数不影响；上下移动，如下： ##

## \-------------0\*\*\*\*\*\*\*\*\*\*\* ##

## \*\*\*\*\*\*\*\*\*\*\*x------------- ##

## x是任意数，现在要把x移上去，那么\*\*\*\*\*\*\*\*\*\*\*中，假设有a个大于x，b个小于x，那么移动之后逆序数就会加上一个b-a，x所能影响的也就是这些罢了，除此之外，其他都不变。接着，如果列数为偶数，那么\*\*\*\*\*\*的个数就是奇数，b,a奇偶性互异，b-a为奇数，所以移动一次后，原序列的逆序数的奇偶性变了。考虑到最后0会移动到最后一行，所以奇偶性会改变n-i次(i为0的行数)，只需判断最后是否是偶数即可。反之，如果列数为奇数，那么\*\*\*\*\*\*的个数就是偶数，b,a奇偶性相同，b-a为偶数，所以移动一次后，原序列的逆序数的奇偶性没变。因为无论怎么移，奇偶性都不变，所以说一开始初态的奇偶性就必须与末态一致。更多关于数码问题的分析可以参考《算法竞赛进阶指南》P39。 ##

## 参考：[https://blog.csdn.net/tmeteorj/article/details/8530105][https_blog.csdn.net_tmeteorj_article_details_8530105]。 ##

## 代码： ##

#include<cstdio>
    #include<cstring>
    using namespace std;
    const int N=1e6+5;
    int ar[N],a[N];
    
    int lowb(int t){
        return t & (-t) ;
    }
    
    void add(int i, int v){
        for ( ; i < N; ar[i] += v, i += lowb(i));
    }
    
    int sum(int i) {
        int s = 0;
        for ( ; i > 0; s += ar[i], i -= lowb(i));
        return s;
    }
    
    int main() {
        int n,m;
        while(scanf("%d%d",&n,&m),n||m) {
            int x,y,t,s=0,nu=0;
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++) {
                    scanf("%d",&t);
                    if(t==0) x=i,y=j;
                    else a[nu++]=t;
                }
            memset(ar,0,sizeof(ar));
            for(int i=nu-1;i>=0;i--) {
                s+=sum(a[i]-1);
                add(a[i],1);
            }
            if(m&1)
                if(s&1) printf("NO\n");
                else    printf("YES\n");
            else
                if(((n-x)^s)&1) printf("NO\n");
                else            printf("YES\n");
        }
        return 0;
    }

[https_blog.csdn.net_tmeteorj_article_details_8530105]: https://blog.csdn.net/tmeteorj/article/details/8530105