转载请注明出处，谢谢：http://www.cnblogs.com/KirisameMarisa/p/4298840.html ---by 墨染之樱花
题目链接：http://poj.org/problem?id=1077
题目描述：民间流传的推15游戏，不过这里简化为3*3，也就是八数码问题，‘x’表示空位。与AOJ0121的“Seven Puzzle”类似。
思路：没什么特别的，构造字符串队列，爆搜一下。注意Hash函数，哈得好就哈哈，哈得不好就只能呵呵了。。。我的hash函数是∑((str[i]*7^i))%1000007外加在x的位置加上i*10007，547MS水过。不过在一样的题hdu1043时限变成了5秒却还是TLE了，果然此题杭电的数据更强，看来是要用A*了。
#include <iostream> #include <ios> #include <iomanip> #include <functional> #include <algorithm> #include <vector> #include <sstream> #include <list> #include <queue> #include <deque> #include <stack> #include <string> #include <set> #include <map> #include <cstdio> #include <cstdlib> #include <cctype> #include <cmath> #include <cstring> #include <climits> using namespace std; #define XINF INT_MAX #define INF 1<<30 #define MAXN 1000007 #define eps 1e-10 #define zero(a) fabs(a)<eps #define sqr(a) ((a)*(a)) #define MP(X,Y) make_pair(X,Y) #define PB(X) push_back(X) #define PF(X) push_front(X) #define REP(X,N) for(int X=0;X<N;X++) #define REP2(X,L,R) for(int X=L;X<=R;X++) #define DEP(X,R,L) for(int X=R;X>=L;X--) #define CLR(A,X) memset(A,X,sizeof(A)) #define IT iterator #define PI acos(-1.0) #define test puts("OK"); #define _ ios_base::sync_with_stdio(0);cin.tie(0); typedef long long ll; typedef pair<int,int> PII; typedef priority_queue<int,vector<int>,greater<int> > PQI; typedef vector<PII> VII; typedef vector<int> VI; #define X first #define Y second inline int Hash(string str) { int len=str.length(),s=7,ans=0; REP(i,len) { if(str[i]>='0' && str[i]<='9') ans+=(str[i]-'0')*s; else ans+=i*10007; s*=7; ans=ans%MAXN; } return ans; } pair<int,int> par[MAXN]; bool vis[MAXN]; int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}}; char direction[4]={'u','d','r','l'}; char ans[100000+10]; void bfs(string start,string end) { CLR(vis,0); queue<string> Q; int s=Hash(start); Q.push(start); vis[s]=1; par[s]=MP(s,-1); while(!Q.empty()) { string temp=Q.front();Q.pop(); if(temp==end) break; int pos; REP(i,9) if(temp[i]=='x') pos=i; int x=pos/3,y=pos%3; REP(i,4) { int tx=x+dir[i][0],ty=y+dir[i][1]; if(tx>=0 && tx<3 && ty>=0 && ty<3) { string next=temp; swap(next[tx*3+ty],next[x*3+y]); int ll=Hash(next); if(!vis[ll]) { par[ll]=MP(Hash(temp),i); vis[ll]=1; Q.push(next); } } } } } int main() {_ string s=""; REP(i,9) { char c; cin>>c; s+=c; } bfs(s,"12345678x"); int res=Hash("12345678x"),tot=0; while(par[res].X!=res) { ans[tot++]=direction[par[res].Y]; res=par[res].X; } for(int i=tot-1;i>=0;i--) cout<<ans[i]; cout<<endl; return 0; }