题目描述

在一个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

(bfs暴搜)

• 先会做AcWing.845 八数码这道题再来看这道.
• 在这基础上，记录bfs最短路的路径，即记录当前状态是由哪个状态转移过来。这道题的状态是用字符串来表示，因此使用哈希表来记录；同时要记录方向，我们就使用unordered_map来存储，key是字符串, value是要记录2个值，所以是pair
• 当找到答案时，从最后一个状态12345678x往前倒推,直到回到初始给定的字符串状态，最后再反向输出即可.
• ps:如果记录由哪个状态转移过来不太懂的话，可以看看yls的算法基础课视频在视频01:12:40处开始，讲的Acwing.844 走迷宫这题有

时间复杂度 $ O(我也不知道) $

C++ 代码

#include <iostream>
#include <queue>
#include <unordered_map>

using namespace std;

bool bfs(string st)
{
    string ed = "12345678x";

    queue<string> q;
    q.push(st);

    unordered_map<string, int> d;
    unordered_map<string, pair<string, int>> Prev;

    d[st] = 0;

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}, dir[4] = {'u', 'r', 'd', 'l'};

    while (q.size()) {
        auto t = q.front();
        q.pop();

        int distance = d[t];

        if (t == ed) { // 如果找到了答案.
            vector<char> res;
            while(distance --)
            {
                auto s = Prev[ed];
                res.push_back(dir[s.second]);
                ed = s.first;
            }

            for(int i = res.size() - 1; i >= 0; i --) cout << res[i];
            return true;
        }

        int k = t.find('x');
        int x = k / 3, y = k % 3;
        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)
            {
                string tmp = t;
                swap(t[k], t[a * 3 + b]);
                if(!d.count(t))
                {
                    d[t] = distance + 1;
                    q.push(t);
                    Prev[t] = {tmp, i};  // 记录状态t是由tmp转移过来, 且方向是i
                }

                swap(t[k], t[a * 3 + b]);
            }
        }
    }

    return false;
}

int main(){
    string str;
    for(int i = 0; i < 9; i ++)
    {
        char c;
        cin >> c;
        str += c;
    }

    if(!bfs(str)) puts("unsolvable"); // 如果找不到答案.

    return 0;
}