首页 > 代码库 > 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"); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。