A*：以(目前步数+估计步数)为关键字优化搜索，这样会先搜离终点近的状态。

在这道题里，估价函数定义为每个非零数位置和他的目标位置的曼哈顿距离。

#include<bits/stdc++.h>
using namespace std;
const int N = 5e2+10;
string s,t="123804765";
int px[]={2,1,1,1,2,3,3,3,2};
int py[]={2,1,2,3,3,3,2,1,1};
unordered_map<string,int>mp;
inline int mabs(int k){if(k<0)k=-k;return k;}
int h(string s){
	int res=0;
	for(register int i = 0; i < 9; i++){
		int k=s[i]-'0';
		if(k==0)continue;
		res+=mabs(px[k]-1-i/3)+mabs(py[k]-1-i%3);
	}
	return res;
}
int bfs(){
	priority_queue<pair<int,string> >q;mp[s]=0;
	q.push({-h(s),s});
	while(!q.empty()){
		string nw=q.top().second;q.pop();int p0=0;string nt=nw;
		if(nw==t)return mp[nw];
		for(register int i = 0; i < 9; i++)if(nw[i]=='0')p0=i;
		if(p0>2){
			swap(nt[p0],nt[p0-3]);
			if(mp.find(nt)==mp.end()){
				mp.emplace(nt,mp[nw]+1);
				q.push({-mp[nt]-h(nt),nt});
			}
			swap(nt[p0],nt[p0-3]);
		}
		if(p0<6){
			swap(nt[p0],nt[p0+3]);
			if(mp.find(nt)==mp.end()){
				mp.emplace(nt,mp[nw]+1);
				q.push({-mp[nt]-h(nt),nt});
			}
			swap(nt[p0],nt[p0+3]);
		}
		if(p0%3){
			swap(nt[p0],nt[p0-1]);
			if(mp.find(nt)==mp.end()){
				mp.emplace(nt,mp[nw]+1);
				q.push({-mp[nt]-h(nt),nt});
			}
			swap(nt[p0],nt[p0-1]);
		}
		if(2-p0%3){
			swap(nt[p0],nt[p0+1]);
			if(mp.find(nt)==mp.end()){
				mp.emplace(nt,mp[nw]+1);
				q.push({-mp[nt]-h(nt),nt});
			}
			swap(nt[p0],nt[p0+1]);
		}
	}
}
int main(){
	cin >> s;
	cout << bfs();
	return 0;
}

130ms目前最优解。

#include <bits/stdc++.h>

using namespace std;

string endd = "123804765";//目标状态 

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

queue<string> q;

map<string, int> dist;//存储当前状态的最小步数 

string s;

int main() {
    cin >> s;
    if (s == endd) {//开始就是目标状态 
   		cout << 0 << endl;
    	return 0; 
	}
    q.push(s);
    dist[s] = 0;//初始化 
    while (!q.empty()) {
        string t = q.front();
        q.pop();
	    int d = dist[t]; 
        if (t == endd) {//当前为目标状态 
        	cout << d;
        	return 0;
		}
        int k = t.find('0');
        int x = k / 3, y = k % 3;//取出0的坐标 
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {//判断边界 
                string change = t;
                swap(change[k], change[nx * 3 + ny]);//改变位置 
                if (dist.find(change) == dist.end()) {//判断是否在之前有过当前状态 
                    dist[change] = d + 1;                    
                    q.push(change);
                }
            }
        }
    }
    return 0;
}