这题贼jiba难，虽然很容易就可以想到是BFS ，但是不用STL的map或者好的hash函数的话很容易超时或者超过内存限制
说出来你可能不信我这道题做了3小时TAT
关键点：
1.用STL map创建hash表，直接搞会超出内存限制
2.BFS 的时候我刚开始是对每一个输入都进行一次BFS ，其实只需要从12345678x进行一次完整的BFS 就可以了，用数组记录path得到答案（我是在数组后加一个a[9]记录father节点的位置）
3.BFS 的顺序无所谓的，oj都会判你对的
#include<iostream> #include<vector> #include<map> #include<deque> using namespace std; vector<short> a; deque<vector<short> > q; map<long,long> pre;//PATH TO HIS FARTHER IN BFS map<long,int> isr;//HASH FUNCTION long exc(vector<short> a){ long sum=0; for(int i=0;i<9;i++){ sum*=10; sum+=a[i]; } return sum; } void PushToDeque(vector<short> test,int t,int n,long father){//PUSH VECTOR INTO DEQUE int pos=test[9]; test[pos]=test[pos+t]; test[pos+t]=0; test[9]+=t; if(isr.find(exc(test))==isr.end()){ isr.insert(pair<long,int>(exc(test),n)); pre.insert(pair<long,int>(exc(test),father)); q.push_back(test); } } int main(){ int N,i,pos; char word[4]={'l','r','u','d'}; char c; long begin; vector<short> temp; for(i=0;i<8;i++) a.push_back(i+1); a.push_back(0); a.push_back(8); begin=exc(a); q.push_back(a); while(!q.empty()){ //BFS 这里只需要一次计算，注意是从12345678x开始BFS而不是从输入案例开始 temp=q.front(); pos=temp[9]; if(pos>2) PushToDeque(temp,-3,4,exc(temp)); if(pos<6) PushToDeque(temp,3,3,exc(temp)); if(pos%3!=0) PushToDeque(temp,-1,2,exc(temp)); if(pos%3!=2) PushToDeque(temp,1,1,exc(temp)); q.pop_front(); } while(cin>>c){//INPUT if(c=='x') a[0]=0; else a[0]=c-'0'; for(i=1;i<9;i++){ cin>>c; if(c=='x') a[i]=0; else a[i]=c-'0'; } long end=exc(a); if(pre.find(end)==pre.end()) cout<<"unsolvable"; else{ while(begin!=end){//OUTPUT cout<<(word[isr[end]-1]); end=pre[end]; } } cout<<endl; } }
