hdu 6620 Just an Old Puzzle（N数码问题）

发布时间：2020-12-13 22:17:12 所属栏目：PHP教程来源：网络整理

导读：http://acm.hdu.edu.cn/showproblem.php?pid=6620 ? N数码问题： n*n矩阵，里面填着1—n*n-1，还有1个空格，通过上下左右移动空格的位置，使矩阵里的数升序排列，空格在右下角。 ? 解的存在性判断结论：（上面的N=n*n-1）将原矩阵从左上角开始展开成一个

http://acm.hdu.edu.cn/showproblem.php?pid=6620

N数码问题：

n*n矩阵，里面填着1—n*n-1，还有1个空格，

通过上下左右移动空格的位置，

使矩阵里的数升序排列，空格在右下角。

解的存在性判断结论：

（上面的N=n*n-1）

将原矩阵从左上角开始展开成一个序列，计算该序列的逆序对数A

将目标矩阵同理计算逆序对数B

逆序对数的计算不包括空格

若n为奇数，A与B奇偶性相同则有解

若n为偶数，设原矩阵空格在第a行，目标矩阵空格在第b行，k=|a-b|

若k为奇数，A与B奇偶性不同则有解

若k为偶数，A与B奇偶性相同则有解

简要理解：

空格左右移动，逆序对数的奇偶性不变

空格上下移动，

若n为偶数，空格与上/下的数m 之间相隔n-1个数，这n-1个数中，若有c个比m小，则有n-1-c个比m大

逆序数改变 |（n-1-c）- c |，即逆序对数改变奇数对

若n为奇数，同理，逆序对数改变偶数对

本题代码：

#include<cstdio>

using namespace std;

int a[17];

int main()
{
    int T;
    scanf("%d",&T);
    int c,d,sum;
    d=4;
    while(T--)
    {
        for(int i=1;i<=16;++i)
        {
            scanf("%d",&a[i]);
            if(!a[i]) c=(i-1)/4+1;
        }
        sum=0; 
        for(int i=1;i<=16;++i)
            if(a[i])
                for(int j=i+1;j<=16;++j)
                    if(a[j])
                        if(a[i]>a[j]) sum++;
        if(!(((d-c)^sum)&1)) printf("Yesn");
        else printf("Non"); 
    } 
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!