83 lines
2.8 KiB
C++
83 lines
2.8 KiB
C++
#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;
|
||
}
|
||
reverse(res.begin(), res.end());
|
||
cout << res << endl;
|
||
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() {
|
||
//加快读入
|
||
cin.tie(0), ios::sync_with_stdio(false);
|
||
|
||
//原始输入是用的一个字符一个空格的形式，无法使用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;
|
||
}
|