八数码求最短步数：
#include<queue>
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
const int LEN = 362880;
struct node
{
int state[9];
int dis;
};
int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
int visited[LEN]={0};
int start[9];
int goal[9];
long int factory[]={1,1,2,6,24,120,720,5040,40320,362880};
void swap(int a,int b)
{
int c=0;
c=a;
a=b;
b=c;
}
bool Cantor(int str[],int n)
{
// cout<<"hello"<<endl;
long result = 0;
for(int i=0;i<n;++i)
{
int counted=0;
for(int j=i+1;j<n;j++)
{
if(str[i]>str[j])
{
++counted;
}
}
result+=counted*factory[n-i-1];
}
if(!visited[result])
{
visited[result]=1;
return 1;
}
else
{
return 0;
}
}
int bfs()
{
node head;
memcpy(head.state,start,sizeof(head.state));
head.dis=0;
queue<node> q;
Cantor(head.state,9);
q.push(head);
while(!q.empty())
{
head = q.front();
q.pop();
int z;
for(z = 0;z<9;z++)
{
if(head.state[z]==0)
{
break;
}
}
int x = z%3;
int y = z/3;
// printf("head.state[%d]=%d",z,head.state[z]);
for(int i=0;i<4;++i)
{
int newx = x + dir[i][0];
int newy = y + dir[i][1];
int nz = newx + 3*newy;
if(newx>=0&&newx<3&&newy>=0&&newy<3)
{
node newnode;
memcpy(&newnode,&head,sizeof(struct node));
int c=newnode.state[z];
newnode.state[z]=newnode.state[nz];
newnode.state[nz]=c;
newnode.dis++;
if(memcmp(newnode.state,goal,sizeof(goal))==0)
{
return newnode.dis;
}
if(Cantor(newnode.state,9))
{
q.push(newnode);
}
}
}
}
return -1;
}
int main()
{
for(int i=0;i<9;++i)
{
cin>>start[i];
// cout<< start[i];
}
cout<<"输入的棋盘："<<endl;
for(int i=1;i<=9;++i)
{
cout<<start[i-1]<<" ";
if(i%3==0)cout<<endl;
}
for(int i=0;i<9;++i) cin>>goal[i];
cout<<"目标的棋盘："<<endl;
for(int i=1;i<=9;++i)
{
cout<<goal[i-1]<<" ";
if(i%3==0)cout<<endl;
}
int num = bfs();
if(num!=-1)
{
cout<<num<<endl;
}
else
{
cout<<"Impossible"<<endl;
}
return 0;
}
八数码求最短路径：
/*
2 3 4 1 5 x 7 6 8
1 2 3 4 6 7 5 8 x
2 3 4 1 5 0 7 6 8
1 2 3 4 5 6 7 8 0
ullddrurdllurdruldr
*/
#include<map>
#include<queue>
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
using namespace std;
const int LEN = 362880;
typedef struct node
{
int state[9];
int dis;
char road;
}node;
int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
char dir_mark[4]={'l','u','r','d'};
int visited[LEN]={0};
int start[9];
int goal[9];
long int factory[]={1,1,2,6,24,120,720,5040,40320,362880};
int flag=1;
string bigparent="";
bool Cantor(int str[],int n)
{
long result = 0;
for(int i=0;i<n;++i)
{
int counted=0;
for(int j=i+1;j<n;j++)
{
if(str[i]>str[j])
{
++counted;
}
}
result+=counted*factory[n-i-1];
}
if(!visited[result])
{
visited[result]=1;
return 1;
}
else
{
return 0;
}
}
int bfs()
{
node head;
memcpy(head.state,start,sizeof(head.state));
head.dis=0;
head.road='0';
queue<node> q;
Cantor(head.state,9);
q.push(head);
map<string,map<string,char> >parent;
string str1="";
for(int i=0;i<9;++i)
{
str1+=head.state[i]+'0';
}
parent[str1]["bigparent"]='0';
while(!q.empty())
{
head = q.front();
q.pop();
int z;
for(z = 0;z<9;z++)
{
if(head.state[z]==0)
{
break;
}
}
int x = z%3;
int y = z/3;
for(int i=0;i<4;++i)
{
int newx = x + dir[i][0];
int newy = y + dir[i][1];
int nz = newx + 3*newy;
if(newx>=0&&newx<3&&newy>=0&&newy<3)
{
node newnode;
memcpy(&newnode,&head,sizeof(struct node));
int c=newnode.state[z];
newnode.state[z]=newnode.state[nz];
newnode.state[nz]=c;
//创建一个parent数组记录个节点的父节点
string str1="";
string str2="";
for(int i=0;i<9;++i)
{
str1+=newnode.state[i]+'0';
str2+=head.state[i]+'0';
}
parent[str1][str2]=dir_mark[i];
// cout<<" parent["<<str1<<"]["<<str2<<"]="<<parent[str1][str2]<<endl;
newnode.dis++;
if(memcmp(newnode.state,goal,sizeof(goal))==0)
{
string rest="",child="",littleparent="";
for(int i=0;i<9;++i)
{
child+=newnode.state[i]+'0';
}
while(1)
{
cout<<"parent["<<child<<"]["<<littleparent<<"]="<<parent[child][littleparent]<<endl;
rest+=parent[child];
child=littleparent;
if(littleparent==bigparent)break;
}
cout<<rest;
flag=0;
return newnode.dis;
}
if(Cantor(newnode.state,9))
{
q.push(newnode);
}
}
}
}
return -1;
}
int main()
{
for(int i=0;i<9;++i)
{
char temp;
cin>>temp;
bigparent+=temp;
if(temp=='x')
{
start[i]=0;
}
else
{
start[i]=temp-'0';
}
// cout<< start[i];
}
cout<<"输入的棋盘："<<endl;
for(int i=1;i<=9;++i)
{
cout<<start[i-1]<<" ";
if(i%3==0)cout<<endl;
}
for(int i=0;i<9;++i)
{
char temp;
cin>>temp;
if(temp=='x')
{
goal[i]=0;
}
else
{
goal[i]=temp-'0';
}
}
cout<<"目标的棋盘："<<endl;
for(int i=1;i<=9;++i)
{
cout<<goal[i-1]<<" ";
if(i%3==0)cout<<endl;
}
bfs();
if(flag)
{
cout<<"unsolvable"<<endl;
}
return 0;
}