Sgu/139

如果0的偏移量和逆序对个数同奇偶则无解。

因为目标状态的偏移量为0，逆序对为15，而0移动的时候偏移量±1，逆序对的改变量也为奇数。

这就使得偏移量和逆序对数始终不是同奇偶。

#include <stdio.h>
using namespace std;
int a[16], res;
int main()
{
    for (int i = 0; i < 16; ++i)
    {
        scanf("%d", &a[i]);
        if (!a[i]) res = 6 - (i % 4) - i / 4;
    }
    for (int i = 0; i < 15; ++i)
        for (int j = i + 1; j < 16; ++j)
            if (a[i] > a[j]) res++;
    if (res & 1) printf("YES");
       else      printf("NO");
    return 0;
}
// From FingerSed

#include<cstdio>
 
const int N=100;
int map[N];
int answer;
//by hza
int main()
{
	freopen("139.in","r",stdin);
	freopen("139.out","w",stdout);
	int i,j;
	for(i=0;i<16;++i)
	{
		scanf("%d",&map[i]);
		if(map[i]==0)
		{
			answer+=(3-i/4);
			continue;
		}
		for(j=0;j<i;++j)
			if(map[j]&&map[j]>map[i])
				++answer;
	}
	if(answer&1)
		printf("NO\n");
	else printf("YES\n");
}