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

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[];

int main()

{

    int T;

    scanf("%d",&T);

    int c,d,sum;

    d=;

    while(T--)

    {

        for(int i=;i<=;++i)

        {

            scanf("%d",&a[i]);

            if(!a[i]) c=(i-)/+;

        }

        sum=;

        for(int i=;i<=;++i)

            if(a[i])

                for(int j=i+;j<=;++j)

                    if(a[j])

                        if(a[i]>a[j]) sum++;

        if(!(((d-c)^sum)&)) printf("Yes\n");

        else printf("No\n");

    }

}

巴特西

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

最新文章

热门文章