题解 | #八数码#

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();
}