#include using namespace std; typedef unordered_map MSI; typedef unordered_map> 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 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; }