You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

79 lines
2.8 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

#include <bits/stdc++.h>
using namespace std;
typedef unordered_map<string, int> MSI;
typedef unordered_map<string, pair<char, string>> MSP;
// 无脑BFS解法
// 2997 ms 可以AC掉本题
string st, ed = "12345678x";
// 上右下左 四个方向
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
char op[] = {'u', 'r', 'd', 'l'};
MSP pre; // 字符串,前驱操作符,前驱字符串
void bfs() {
queue<string> q;
MSI dist; // 标识某个状态是否用过,如果用过,那么记录的最短距离是多少
// 入队列
q.push(st);
dist[st] = 0; // 记录出发点最短距离
// 开始bfs
while (q.size()) {
// 取出队头字符串
string t = q.front();
q.pop();
// 如果到达最终状态,结束
if (t == ed) {
string res;
while (ed != st) {
res += pre[ed].first;
ed = pre[ed].second;
}
for (int i = res.size() - 1; i >= 0; i--) cout << res[i];
break;
}
int d = dist[t]; // 现在记录的最短路径长度
int k = t.find('x'); // 在字符串t中查找x的索引位置
int tx = k / 3, ty = k % 3; // 映射的二维数组中的行与列
for (int i = 0; i < 4; i++) { // 枚举四个方向
int x = tx + dx[i], y = ty + dy[i]; // 目标位置
if (x < 0 || x >= 3 || y < 0 || y >= 3) continue; // 出界
string v = t;
swap(v[x * 3 + y], v[k]); // x与目标位置交换一下
if (!dist.count(v)) { // 如果t字符串出现过注意C++取unorderd_map是否存在元素时需要用count
dist[v] = d + 1; // 记录是上一个距离+1得到的
q.push(v); // 新位置进入队列
pre[v] = {op[i], t}; // 记录v这个字符串的前驱字符串是t并且是通过操作符op[i]转化而来
}
}
}
}
int main() {
// 原始输入是用的一个字符一个空格的形式无法使用string进行读入
char c;
for (int i = 0; i < 9; i++) cin >> c, st += c;
// 八数码定理:检查逆序对数量
int nums = 0;
for (int i = 0; i < 9; i++) {
if (st[i] == 'x') continue; // 保证不是x
for (int j = i + 1; j < 9; j++) {
if (st[j] == 'x') continue; // 保证不是x
if (st[j] < st[i]) nums++; // 逆序数
}
}
// 如果逆序对数量是奇数个,则输出-1
if (nums & 1)
puts("unsolvable");
else // 否则通过bfs输出路径
bfs();
return 0;
}