在一个?3×3 的网格中，1～8?这?8?个数字和一个?X?恰好不重不漏地分布在这?3×3 的网格中。
例如：
1 2 3
X 4 6
7 5 8
在游戏过程中，可以把?X?与其上、下、左、右四个方向之一的数字交换（如果存在）。
我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
1 2 3
4 5 6
7 8 X
例如，示例中图形就可以通过让?X?先后与右、下、右三个方向的数字交换成功得到正确排列。
交换过程如下：
1 2 3 1 2 3 1 2 3 1 2 3
X 4 6 4 X 6 4 5 6 4 5 6
7 5 8 7 5 8 7 X 8 7 8 X
把?X?与上下左右方向数字交换的行动记录为?u、d、l、r。
现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。
输入占一行，将?3×3 的初始网格描绘出来。
例如，如果初始网格如下所示：
1 2 3
x 4 6
7 5 8
则输入为：1 2 3 x 4 6 7 5 8
输出占一行，包含一个字符串，表示得到正确排列的完整行动记录。
如果答案不唯一，输出任意一种合法方案即可。
如果不存在解决方案，则输出?unsolvable。
2 3 4 1 5 x 7 6 8
ullddrurdllurdruldr性质：当所给输入有答案的充分必要条件是输入的逆序对为偶数
对于估计距离，我们可以使用哈密顿距离作为估计距离?
A*算法为BFS的优化算法：?
2.1.3 BFS中的双向广搜和A-star - AcWing
?
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
using namespace std;
typedef long long LL;
string start, s;
typedef pair<int, string> PIS;
int F(string u) {
int ret = 0;
for (int i = 0; i < 8; i++) {
int t = u[i] - '1';
int x = i / 3, y = i % 3;
ret += abs(x - t / 3) + abs(y - t % 3);
}
return ret;
}
string Astar() {
char dir[] = "urdl";
unordered_map<string, int>dist;
unordered_map<string, pair<string, char>>pre;
priority_queue<PIS, vector<PIS>, greater<PIS>>q;
int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
dist[start] = 0;
q.push({ dist[start],start });
PIS t;
while (!q.empty()) {
t = q.top();
q.pop();
if (t.second == "12345678x")break;
int x = 0, y = 0;
for (int i = 0; i < t.second.size(); i++) {
if (t.second[i] == 'x') {
x = i / 3, y = i % 3;
break;
}
}
string tmp;
for (int i = 0; i < 4; i++) {
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a >= 3 || b < 0 || b >= 3)continue;
tmp = t.second;
swap(tmp[a * 3 + b], tmp[x * 3 + y]);
if (dist.count(tmp) == 0 || dist[tmp] > dist[t.second] + 1) {
dist[tmp] = dist[t.second] + 1;
pre[tmp] = { t.second,dir[i] };
q.push({ dist[tmp]+F(tmp),tmp});
}
}
}
string ret,tmp="12345678x";
while (tmp != start) {
ret += pre[tmp].second;
tmp = pre[tmp].first;
}
reverse(ret.begin(), ret.end());
return ret;
}
int main() {
string ch;
for (int i = 1; i <= 9; i++) {
cin >> ch;
if (ch != "x")s += ch;
start += ch;
}
int cnt = 0;
for (int i = 0; i < 8; i++) {
for (int j = i + 1; j < 8; j++) {
if (s[i] > s[j])cnt++;
}
}
//cout << cnt << endl;
if (cnt & 1)cout << "unsolvable" << endl;
else {
cout << Astar() << endl;
}
return 0;
}?本题直接暴搜也能过：
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
using namespace std;
typedef long long LL;
string start, s;
typedef pair<int, string> PIS;
string Astar() {
char dir[] = "urdl";
unordered_map<string, int>dist;
unordered_map<string, pair<string, char>>pre;
priority_queue<PIS, vector<PIS>, greater<PIS>>q;
int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
dist[start] = 0;
q.push({ dist[start],start });
PIS t;
while (!q.empty()) {
t = q.top();
q.pop();
if (t.second == "12345678x")break;
int x = 0, y = 0;
for (int i = 0; i < t.second.size(); i++) {
if (t.second[i] == 'x') {
x = i / 3, y = i % 3;
break;
}
}
string tmp;
for (int i = 0; i < 4; i++) {
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a >= 3 || b < 0 || b >= 3)continue;
tmp = t.second;
swap(tmp[a * 3 + b], tmp[x * 3 + y]);
if (dist.count(tmp) == 0 || dist[tmp] > dist[t.second] + 1) {
dist[tmp] = dist[t.second] + 1;
pre[tmp] = { t.second,dir[i] };
q.push({ dist[tmp],tmp });
}
}
}
string ret,tmp="12345678x";
while (tmp != start) {
ret += pre[tmp].second;
tmp = pre[tmp].first;
}
reverse(ret.begin(), ret.end());
return ret;
}
int main() {
string ch;
for (int i = 1; i <= 9; i++) {
cin >> ch;
if (ch != "x")s += ch;
start += ch;
}
int cnt = 0;
for (int i = 0; i < 8; i++) {
for (int j = i + 1; j < 8; j++) {
if (s[i] > s[j])cnt++;
}
}
//cout << cnt << endl;
if (cnt & 1)cout << "unsolvable" << endl;
else {
cout << Astar() << endl;
}
return 0;
}