emmm,其实也不算很难的思路,就是用mp去重并记录走过的路径,就ok了这道题,只需要一个记录路径的mp就行了,map多了会爆内存(别问我是怎么知道的qaq),对了,还有就是二维一维坐标相互转换的方法,最顶上三个函数就是了。
#include<bits/stdc++.h>
using namespace std;
string s;
string en="12345678x";
map<string,string> mp;
queue<string> q;
int posx(int x){
return x/3;
}
int posy(int x){
return x%3;
}
int tol(int x,int y){
return x*3+y;
}
int findp(string x){
for(int i=0;i<x.length();i++){
if(x[i]=='x')
return i;
}
return -1;
}
int mov[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
char step[4]={'d','u','r','l'};
bool check(int x,int y){
return x>=0&&x<3&&y>=0&&y<3;
}
string bfs(){
while(!q.empty()){
string tmp=q.front();
q.pop();
if(tmp==en) return mp[tmp];
int getpos=findp(tmp);
int x=posx(getpos); int y=posy(getpos);
string now=mp[tmp];
for(int i=0;i<4;i++){
int xx=x+mov[i][0]; int yy=y+mov[i][1];
if(check(xx,yy)){
int p=tol(xx,yy);
swap(tmp[getpos],tmp[p]);
if(!mp.count(tmp)){
mp[tmp]=now+step[i];
q.push(tmp);
}
swap(tmp[getpos],tmp[p]);
}
}
}
return "unsolvable";
}
int main(){
char tmp[2];
for(int i=0;i<9;i++){
cin>>tmp;
s+=*tmp;
}
q.push(s);
mp[s]="";
cout<<bfs();
}