首页 > 代码库 > sgu139Help Needed!判断15数码是否有解,以及判断N数码是否有解的推论

sgu139Help Needed!判断15数码是否有解,以及判断N数码是否有解的推论

是这样的,要你判断一个15数码是否有解。

我不会,找了这样一个方法。

将16个数按出现顺序存放在一维数组里面,

然后累加每个数的逆序对数目,

还要加上0到终态的曼哈顿距离,得到一个数x。

由于最后的状态,整个图的逆序对数目是15,

是个奇数,于是,如果x也是奇数,

那么这个15数码就有解,

否则无解。

其它各种数码,都按照此法解就是了,

我的代码如下:

#include<iostream>
using namespace std;
int main()
{
	int map[16],ans=0;
	for(int i=0;i<16;i++)
	{
		scanf("%d",&map[i]);
		if(!map[i])
			ans+=6-i%4-i/4;
		for(int j=0;j<i;j++)
			if(map[j]>map[i])
				ans++;
	}
	if(ans&1)
		printf("YES");
	else
		printf("NO");
}