A star/A * 路径规划算法

曼哈顿距离介绍: 详情

曼哈顿距离是种使用在几何度量空间的几何学用语，用以标明两个点在标准坐标系上的绝对轴距总和。也就是红线代表曼哈顿距离

AC代码

参考答案：

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

using namespace std;

queue<string> q;
unordered_map<string, int>d;

int bfs(string start)
{
    string end = "12345678x";
    q.push(start);
    d[start] = 0;

    while (q.size())
    {
        int dx[4] = { 0,0,-1,1 }, dy[4] = { 1,-1,0,0 };
        string t = q.front();
        int dis = d[t];
        q.pop();
        if (t == end) return dis;
        int k = t.find('x');
        int a = k / 3, b = k % 3;//一维转二维;
        for (int i = 0; i < 4; ++i)
        {
            int x = a + dx[i], y = b + dy[i];//二维转一维;
            if (x >= 0 && x < 3 && y >= 0 && y < 3)
            {
                swap(t[k], t[x * 3 + y]);
                if (!d[t])
                {
                    d[t] = dis + 1;
                    q.push(t);
                }
                swap(t[k], t[x * 3 + y]);
            }
        }
    }

    return -1;
}
int main()
{
    char ch[2];
    string start;

    for (int i = 1; i <= 9; ++i)
    {
        scanf("%s", ch);
        start += *ch;
    }

    cout << bfs(start) << endl;

    return 0;
}