八數碼問題
Input
You will receive, several descriptions of configuration of the 8 puzzle. One description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and the tiles listed from left to right within a row, where the tiles are
represented by numbers 1 to 8, plus 'x'. For example, this puzzle
1 2 3
x 4 6
7 5 8
is described by this list:
1 2 3 x 4 6 7 5 8
Output
You will print to standard output either the word ``unsolvable'', if the puzzle has no solution, or a string consisting entirely of the letters 'r', 'l', 'u' and 'd' that describes a series of moves that produce a solution. The string should include no spaces
and start at the beginning of the line. Do not print a blank line between cases.
Sample Input
2 3 4 1 5 x 7 6 8
Sample Output
ullddrurdllurdruldr
一、數據如何存儲和表示？
1、可以用整形來表示八數碼的狀態，x可以當作“9”，“0”不好處理，例如終態12345678x，可以表示成整數123456789，
2、用數組來存儲，這裡x可以用0或9來表示。
二、數據如何拓展？
1、對於int型整數，數據的拓展就是對這個數的處理，例如對於整數
1 2 3 1 2 3
4 5 6 4 5 9
7 8 9 x上移一位變成的狀態是 7 8 6 即整數123459786
2、對於數組，數據拓展就是將該數組看成是二維數組，對此二維數組行和列的處理
三、如何記錄路徑？
1、構造一張鄰接表，鏈式或者是連續存儲都可以，記錄每個節點的父節點和所有子節點，最後從目的節點遞歸輸出最短路徑，不用耗費大量內存記錄走過的路徑，所以極力推薦此種實現方法，具體應用可以參見
LeetCode OJ:Word Ladder II 解題思路過程詳談
2、因為此題只是記錄udlr，所以可以用string來記錄，不過因為對每個路徑都需要存儲走過的路徑，太耗內存，所以不推薦
四、如何判重？
1、對於int型數組，可以構造一個大數組，記錄是否訪問，如vis[123456789]表示123456789狀態是否訪問，優點：快速。缺點：大量數據浪費，int類型大小的局限性
2、對於數組，可以將數組變成int型，再進行操作
3、用map來存，避免大量浪費
4、用康托拓展判重
五、狀態轉移如何建立？
1、最簡單的無非是廣搜，
（1）正向廣搜
（2）反向廣搜，將所有可能點都記錄下來，用string[]大數組存儲所有路徑，當輸入數據次數較多時比較適用，因為廣搜只進行1次，內存消耗太大
2、雙向廣搜
3、A*算法
4、IDA*算法
這裡提供一個使用雙向廣搜+map+int型存儲數據版，答案不對，僅供參考
#include
#include
再提供一個反向廣搜版+康托版
/*
HDU 1043 Eight
思路：反向搜索，從目標狀態找回狀態對應的路徑
用康托展開判重
*/
#include
#include
#include
#include
#include
using namespace std;
const int MAXN=1000000;//最多是9!/2
int fac[]={1,1,2,6,24,120,720,5040,40320,362880};//康拖展開判重
// 0!1!2!3! 4! 5! 6! 7! 8! 9!
bool vis[MAXN];//標記
string path[MAXN];//記錄路徑
int cantor(int s[])//康拖展開求該序列的hash值
{
int sum=0;
for(int i=0;i<9;i++)
{
int num=0;
for(int j=i+1;j<9;j++)
if(s[j]q;
q.push(cur);
path[aim]="";
while(!q.empty())
{
cur=q.front();
q.pop();
int x=cur.loc/3;
int y=cur.loc%3;
for(int i=0;i<4;i++)
{
int tx=x+dir[i][0];
int ty=y+dir[i][1];
if(tx<0||tx>2||ty<0||ty>2)continue;
next=cur;
next.loc=tx*3+ty;
next.s[cur.loc]=next.s[next.loc];
next.s[next.loc]=0;
next.status=cantor(next.s);
if(!vis[next.status])
{
vis[next.status]=true;
next.path=indexs[i]+next.path;
q.push(next);
path[next.status]=next.path;
}
}
}
}
int main()
{
freopen("C:\\in.txt","r",stdin);
char ch;
Node cur;
bfs();
while(cin>>ch)
{
if(ch=='x') {cur.s[0]=0;cur.loc=0;}
else cur.s[0]=ch-'0';
for(int i=1;i<9;i++)
{
cin>>ch;
if(ch=='x')
{
cur.s[i]=0;
cur.loc=i;
}
else cur.s[i]=ch-'0';
}
cur.status=cantor(cur.s);
if(vis[cur.status])
{
cout<
最後，再提供一個A*+康托版
#include
#include
#include
#include
#include
using namespace std;
const int MAXN=1000000;
int fac[]={1,1,2,6,24,120,720,5040,40320,362880};//康拖展開判重
// 0!1!2!3! 4! 5! 6! 7! 8! 9!
bool vis[MAXN];//標記
string path;//記錄最終的路徑
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//方向向量
char indexs[5]="udlr";//正向搜索
struct Node
{
int data[9];
int f,g,h;
int loc;//“0”的位置,把“x"當0
int status;//康拖展開的hash值
string path;//路徑
bool operator==(const Node &t){
return status==t.status;
}
bool operator<(const Node &t)const{
return f>t.f;
}
}start,goal;//起始和終止點
int Cantor(int s[])//康拖展開求該序列的hash值
{
int sum=0;
for(int i=0;i<9;i++)
{
int num=0;
for(int j=i+1;j<9;j++)
if(s[j] q;
q.push(start);
while(!q.empty())
{
cur=q.top();
q.pop();
if(cur==goal)
{
path=cur.path;
return true;
}
int x=cur.loc/3;
int y=cur.loc%3;
for(int i=0;i<4;i++)
{
int tx=x+dir[i][0];
int ty=y+dir[i][1];
if(tx<0||tx>2||ty<0||ty>2)continue;
next=cur;
next.loc=tx*3+ty;
next.data[cur.loc]=next.data[next.loc];
next.data[next.loc]=0;
next.status=Cantor(next.data);
if(!vis[next.status])
{
vis[next.status]=true;
next.path=next.path+indexs[i];
if(next==goal)
{
path=next.path;
return true;
}
next.g++;//g值
next.f=Fvalue(next,goal,1);//f值
q.push(next);
}
}
}
return false;
}
int main()
{
freopen("C:\\in.txt","r",stdin);
char ch;
//目的節點初始化start
for(int i=0;i<8;i++)goal.data[i]=i+1;
goal.data[8]=0;
goal.status=46234;//123456780對應的康拖展開的hash值
//end
while(cin>>ch)
{
//起始節點初始化start
if(ch=='x') {start.data[0]=0;start.loc=0;}
else start.data[0]=ch-'0';
for(int i=1;i<9;i++)
{
cin>>ch;
if(ch=='x')
{
start.data[i]=0;
start.loc=i;
}
else start.data[i]=ch-'0';
}
start.status=Cantor(start.data);//康拖hash值
start.g=0;
start.f=Fvalue(start,goal,1);//計算f值
//end
if(Astar())
{
cout<
