179. 八数码 题解

// 普通BFS解法
#include <bits/stdc++.h>
using namespace std;

char d[5] = "drul";
int dx[] = {1,0,-1,0}, dy[] = {0,1,0,-1};
string ed = "12345678x";  // 目标状态
unordered_map<string,int> p;  // 记录操作类型
unordered_map<string,string> pre;  // 记录路径

bool bfs(string s)
{
    queue<string>q;
    q.push(s);

    while (q.size())
    {
        auto t = q.front();
        q.pop();
        string h = t;  // 备份
        if (t == ed)    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)
            {
                int temp = a * 3 + b;  // 计算转为序列后'x'所处的位置
                swap(t[k], t[temp]);
                if (!p.count(t))  // 如果之前没有访问过
                {
                    p[t] = i;  // 记录操作类型
                    pre[t] = h;  // 记录前驱序列
                    q.push(t);
                }
                swap(t[k], t[temp]);  // 还原为原序列，以便进行其他操作
            }            
        }
    }
    return false;
}

int main()
{
    string s, c;
    for (int i = 0; i < 9; i++) cin >> c, s += c;

    if (bfs(s))
    {
        vector<char>arr;
        string t = ed;
        while (t != s)  // 输出路径
        {
            arr.push_back(d[p[t]]);  // d[]是为了取出操作类型
            t = pre[t];  // 转移到下一个序列
        }
        reverse(arr.begin(), arr.end());
        for (auto x : arr)  cout << x;
    }
    else cout << "unsolvable" << endl;
    
    return 0;
}

// A*寻路解法
#include <bits/stdc++.h>
using namespace std;

int f(string state)  // 估计函数
{
    int res = 0;
    for (int i = 0; i < state.size(); i++)
        if (state[i] != 'x')  
        {
            int t = state[i] - '1';  // -'1'是因为“12...x”是从1开始的
            res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);  // 曼哈顿距离
        }
    return res;
}

string bfs(string start)
{
    int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};
    char op[4] = {'u','r','d','l'};  // 要将操作数组与坐标变化数组一一对应
    string end = "12345678x";  // 终点
    unordered_map<string, pair<string,char> > prev;  // 存储一个元素由哪种状态,经过哪种操作得来
    unordered_map<string, int> dist;  
    // 小根堆,将元素的估计终点距离从小到大排序
    priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>> > q;

    q.push({f(start), start});  // 加入起点
    dist[start] = 0;  // 起点到起点的距离为0

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

        string state = t.second;
        if (state == end)  break;  // 终点出列的话就退出

        int x, y;  // 查找x的横纵坐标
        for (int i = 0; i < state.size(); i++)
            if (state[i] == 'x')
            {
                x = i / 3, y = i % 3;
                break;
            }
        
        string source = state;
        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)  // 矩阵边界
            {
                swap(state[x * 3 + y], state[a * 3 + b]);
                if (!dist.count(state) || dist[state] > dist[source] + 1)  // 如果没有被记录或者小于记录值
                {
                    dist[state] = dist[source] + 1;  // 更新距离
                    prev[state] = {source, op[i]};  // 标记由哪种状态转移而来,并且记录执行的操作
                    q.push({f(state) + dist[state], state});
                }
                swap(state[x * 3 + y], state[a * 3 + b]);  // 因为要扩展到四个方向,所以要还原
            }
        }
    }

    string res;
    while (end != start)
    {
        res += prev[end].second;
        end = prev[end].first;
    }
    reverse(res.begin(), res.end());
    return res; 
}


int main()
{
    string g, c, seq;
    while (cin >> c)
    {
        g += c;
        if (c != "x")   seq += c;
    }

    int t = 0;  // 统计逆序对的数量
    for (int i = 0; i < seq.size(); i++)
        for (int j = i + 1; j < seq.size(); j++)
            if (seq[i] > seq[j])  t++;

    if (t % 2)  cout << "unsolvable";  // 如果逆序对为奇数,就不可能抵达终点
    else  cout << bfs(g);

    return 0;
}