目录
POJ1077Eight
1.直接广搜，超时
2.用A*实现搜索——AC
POJ1077Eight
1.直接广搜，超时
//POJ1077直接广搜超时。。。
#include<iostream>
#include<cmath>
#include<string>
#include<map>
#include<queue>
using namespace std;
#define N 3
#define N2 9struct Puzzle{int f[N2]; //当前状态的数组int space; //八数码中空格所对应的f[i]中的下标istring path;bool operator < (const Puzzle &p) const {for(int i=0;i<N2;i++){if(f[i]==p.f[i]) continue;return f[i]>p.f[i];}return false;}
};static const int dx[4]={-1,0,1,0};
static const int dy[4]={0,-1,0,1};
static const char dir[4]={'u','l','d','r'};bool isTarget(Puzzle p){ //判断当前状态是不是目标状态for(int i=0;i<N2;i++)if(p.f[i]!=(i+1)) return false;return true;
}string bfs(Puzzle s){queue<Puzzle> Q;map<Puzzle,bool> V; //标记状态，初始时,全部默认为falsePuzzle u,v;s.path="";Q.push(s);V[s]=true;while(!Q.empty()){u=Q.front(); Q.pop();//cout<<"u.path="<<u.path<<endl;if(isTarget(u)) return u.path;int sx=u.space/N; //空格的坐标int sy=u.space%N;for(int r=0;r<4;r++){int tx=sx+dx[r];int ty=sy+dy[r];if(tx<0||ty<0||tx>=N||ty>=N) continue;v=u;swap(v.f[u.space],v.f[tx*N+ty]); //换格子v.space=tx*N+ty; //记录当前状态下空格的位置if(!V[v]){ //如果当前状态没有访问过，将当前状态压入队列中V[v]=true;v.path+=dir[r]; //存储路径，直接字符串连接+即可Q.push(v);}}}return "unsolvable";
}int main(){Puzzle in;char ch;for(int i=0;i<N2;i++){cin>>ch;if(ch=='x'){in.f[i]=N2; //set spacein.space=i;}else in.f[i]=ch-'0';//cout<<"***="<<in.f[i]<<endl;}string ans=bfs(in);cout<<ans<<endl;return 0;
}
2.用A*实现搜索——AC
//A*
#include<iostream>
#include<cmath>
#include<string>
#include<map>
#include<queue>
using namespace std;
#define N 3
#define N2 9
static const int dx[4]={-1,0,1,0};
static const int dy[4]={0,-1,0,1};
static const char dir[4]={'u','l','d','r'};
int MDT[N2][N2];struct Puzzle{int f[N2];int space; //八数码中空格所对应的f[i]中的下标iint MD,cost;int pre;string path;bool operator < (const Puzzle &p) const {for(int i=0;i<N2;i++){if(f[i]==p.f[i]) continue;return f[i]<p.f[i];}return false;}
};struct State{Puzzle puzzle;int estimated;bool operator < (const State &s)const{return estimated>s.estimated; //在优先队列中，曼哈顿距离越小，优先级越高}
};int getAllMD(Puzzle pz){int sum=0;for(int i=0;i<N2;i++){if(pz.f[i]==N2) continue;sum+=MDT[i][pz.f[i]-1];}return sum;
}string astar(Puzzle s){priority_queue<State> PQ;s.MD=getAllMD(s);s.cost=0;s.path="";s.pre=-1;map<Puzzle,bool> V; //标记状态，初始时,全部默认为falsePuzzle u,v;State initial;initial.puzzle=s;initial.estimated=getAllMD(s);PQ.push(initial);while(!PQ.empty()){State st=PQ.top(); PQ.pop();u=st.puzzle;if(u.pre!=-1) u.path+=dir[u.pre];if(u.MD==0) return u.path;V[u]=true;int sx=u.space/N; //空格的坐标int sy=u.space%N;for(int r=0;r<4;r++){int tx=sx+dx[r];int ty=sy+dy[r];if(tx<0||ty<0||tx>=N||ty>=N) continue;v=u;v.MD-=MDT[tx*N+ty][v.f[tx*N+ty]-1];v.MD+=MDT[sx*N+sy][v.f[tx*N+ty]-1];swap(v.f[sx*N+sy],v.f[tx*N+ty]); //换格子v.space=tx*N+ty; //记录当前状态下空格的位置if(!V[v]){v.cost++;v.pre=r;State news;news.puzzle=v;news.estimated=v.cost+v.MD;PQ.push(news);}}}return "unsolvable";
}int main(){for(int i=0;i<N2;i++)for(int j=0;j<N2;j++)MDT[i][j]=abs(i/N-j/N)+abs(i%N-j%N);Puzzle in;char ch;for(int i=0;i<N2;i++){cin>>ch;if(ch=='x'){in.f[i]=N2; //set spacein.space=i;}else in.f[i]=ch-'0';//cout<<"***="<<in.f[i]<<endl;}cout<<astar(in)<<endl;return 0;
}