#include?“calres.h“
#include?

const?int?MAXN?=?362890;
int?fac[9]?=?{112624120720504040320};
int?res[9]?=?{123456780};
int?vis[MAXN];
????????????????//???右????下????左?????上
int?nextDir[4][2]?=?{{01}{10}{0-1}{-10}};
char?chDir[5]?=?“l(fā)urd“;
char?path[200];
int?length;
GYH::node?que[400000];

int?GYH::getLength（）
{
????return?length;
}

char*?GYH::getResult（）
{
????return?path;
}

void?GYH::swap（int?*a?int?*b）
{
????int?temp?=?*a;
????*a?=?*b;
????*b?=?temp;
}

int?GYH::Cantor（int?*s）
{
????int?ijnumtemp;
????num?=?0;
????for（i?=?0;?i?????{
????????temp?=?0;
????????for（j?=?i+1;?j?????????????if（s[j]?????????num?+=?fac[8-i]*temp;
????}
????return?num;
}

void?GYH::CantorReverse（int?*s?int?val）
{
????int?flag[10];
????memset（flag0sizeof（flag））;
????for（int?i?=?0;?i?????{
????????int?rk?=?val/fac[8-i];
????????for（int?j?=?0;?j?<=?rk;?++j）
????????????if（flag[j]）?++rk;
????????s[i]?=?rk;
????????flag[rk]?=?1;
????????val?=?val%fac[8-i];
????}
}

void?GYH::createPath（int?index）
{
????if（que[index].parent?==?-1）
????????return;
????createPath（que[index].parent）;
????path[length++]?=?que[index].dir;
}

void?GYH::BFS（int?*s）
{
????int?ans?=?Cantor（res）;
????int?num[9]position;
????for（int?i?=?0;?i?????{
????????num[i]?=?s[i];
????????if（s[i]?==?0）
????????????position?=?i;
????}
????memset（vis0sizeof（vis））;
????int?head?=?0tail?=?0;
????que[tail].parent?=?-1;
????que[tail].pos?=?position;
????que[tail].status?=?Cantor（num）;
????vis[que[tail].status]?=?1;
????++tail;

????while（head?????{
????????node?cur?=?que[head];
????????int?x?=?cur.pos/3;
????????int?y?=?cur.pos%3;
????????int?txty;
????????for（int?k?=?0;?k?????????{
????????????tx?=?x?+?nextDir[k][0];
????????????ty?=?y?+?nextDir[k][1];
????????????if（tx??2?||?ty?>?2）?continue;
????????????CantorReverse（numcur.status）;
????????????int?newPos?=?tx*3+ty;
????????????swap（&num[newPos]&num[cur.pos]）;
????????????int?newStatus?=?Cantor（num）;
????????????if（vis[newStatus]?==?0）
????????????{
????????????????vis[newStatus]?=?1;
????????????????node?sub;
????????????????sub.parent?=?head;
????????????????sub.status?=?newStatus;
????????????????sub.pos?=?newPos;
????????????????//這是之前的狀態(tài)移動到當(dāng)前狀態(tài)的移動方向
????????????????sub.dir?=?chDir[k];
????????????????que[tail++]?=?sub;

????????????????if（newStatus?==?ans）
????????????????{
????????????????????length?=?0;
????????????????????createPath（tail-1）;
????????????????????return;
????????????????}
????????????}
????????}
????????++head;
????}
}

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----

?????文件????????116??2012-09-13?12:24??jigsaw\background.png

?????文件???????2779??2017-02-27?23:44??jigsaw\calres.cpp

?????文件????????314??2017-02-27?23:42??jigsaw\calres.h

?????文件????????112??2017-02-24?16:09??jigsaw\img.qrc

?????文件????????407??2017-02-27?23:38??jigsaw\jigsaw.pro

?????文件????????175??2017-02-24?15:59??jigsaw\main.cpp

?????文件???????6764??2017-02-28?00:02??jigsaw\widget.cpp

?????文件???????1201??2017-02-28?00:00??jigsaw\widget.h

?????目錄??????????0??2017-03-31?22:01??jigsaw

-----------?---------??----------?-----??----

????????????????11868????????????????????9