648 条评论
-
-
#include<bits/stdc++.h> using namespace std;
struct node { int g; // 实际步数 int h; // 启发值 int f; // g + h string s;
node(int _g, string _s) : g(_g), s(_s) { h = get_h(s); f = g + h; } // 计算曼哈顿距离 static int get_h(const string& s) { int ans = 0; for (int i = 0; i < 9; i++) { if (s[i] == '0') continue; // 如果是0（空格），跳过 int num = s[i] - '0' - 1; // 数字1-9对应目标位置0-8 int cur_r = i / 3, cur_c = i % 3; int target_r = num / 3, target_c = num % 3; ans += abs(cur_r - target_r) + abs(cur_c - target_c); } return ans; }};
struct cmp { bool operator()(const node& a, const node& b) const { return a.f > b.f; // 小顶堆 } };
// 预先计算所有可能的交换对（去重后的相邻位置对） vector<pair<int, int>> edges = { {0,1}, {0,3}, {1,2}, {1,4}, {2,5}, {3,4}, {3,6}, {4,5}, {4,7}, {5,8}, {6,7}, {7,8} };
int main() { ios::sync_with_stdio(false); cin.tie(0);
string start = ""; int a; for (int i = 0; i < 9; i++) { cin >> a; start += char('0' + a); } string target = "123456789"; // 如果已经有序 if (start == target) { cout << 0 << endl; return 0; } priority_queue<node, vector<node>, cmp> pq; unordered_map<string, int> dist; // 记录每个状态的最小步数 pq.push(node(0, start)); dist[start] = 0; while (!pq.empty()) { node cur = pq.top(); pq.pop(); // 如果当前不是最优解，跳过 if (cur.g != dist[cur.s]) continue; // 到达目标 if (cur.s == target) { cout << cur.g << endl; return 0; } // 扩展邻居 for (auto& edge : edges) { string next_s = cur.s; swap(next_s[edge.first], next_s[edge.second]); int next_g = cur.g + 1; // 如果未访问过，或者找到更优路径 if (dist.find(next_s) == dist.end() || next_g < dist[next_s]) { dist[next_s] = next_g; pq.push(node(next_g, next_s)); } } } cout << -1 << endl; return 0;}
