记录编号	610255	评测结果	AAAAAAAAAA
题目名称	八数码问题	最终得分	100
用户昵称	终焉折枝	是否通过	通过
代码语言	C++	运行时间	0.046 s
提交时间	2025-12-18 22:53:37	内存使用	3.79 MiB

#include<iostream>
#include<cmath>
#include<unordered_map>
#include<queue>
using namespace std;

string s;
int xx[] = {1, 0, 0, 0, 1, 2, 2, 2, 1};
int yy[] = {1, 0, 1, 2, 2, 2, 1, 0, 0};
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int f(string now){
	int sum = 0;
	for(int i = 0;i < 9;i ++){
		int x = i / 3, y = i % 3;
		int p = x * 3 + y;
		int v = now[p] - '0';
		sum += (abs(x - xx[v]) + abs(y - yy[v]));
	}
	return sum;
}

int Astar(string now){
	unordered_map<string, int> d;
	priority_queue<pair<int, string> > q;
	string tag = "123804765";
	q.push(make_pair(-f(now), now));
	d[now] = 0;
	while(!q.empty()){
		string u = q.top().second;
		if(u == tag) return d[tag];
		q.pop();
		int k = u.find('0');
		int x = k / 3, y = k % 3;
		for(int i = 0;i < 4;i ++){
			int nx = x + dx[i], ny = y + dy[i];
			if(nx < 0 || ny < 0 || nx >= 3 || ny >= 3) continue;
			if(nx * 3 + ny > 8 || nx * 3 + ny < 0) continue;
			string t = u;
			swap(t[x * 3 + y], t[nx * 3 + ny]);
			if(!d.count(t)){
				d[t] = d[u] + 1;
				q.push(make_pair(-f(t) - d[t], t));
			}
		}
	}
	return d[tag];
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> s;
	cout << Astar(s) << '\n';
	return 0;
}