题目：八数码

普通BFS

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <set>
using namespace std;

unordered_map<string, bool> check;
unordered_map<string, pair<char, string>> parent;


int dx[] = {-1, 0, +1, 0};
int dy[] = {0, +1, 0, -1};
char op[] = {'u','r','d','l'};

bool has_ans(string &state)
{

    int cnt = 0;
    int len = state.size();
    for(int i = 0; i < len; i++)
    {
        for(int j = i; j < len ; j++)
            if(state[i] == 'x' || state[j] == 'x' || state[i] <= state[j]) continue;
            else cnt++; 
    }

    return (cnt % 2) == 0;
}

string bfs(string &start)
{
    string end = "12345678x";
    queue<string> q;
    q.push(start);
    check[start] = true;
    parent[start] = {'0',"grandfather"};

    while(q.size())
    {
        string t = q.front(); q.pop();
        if(t == end) break;
        int x = 0, y = 0;
        for(int i = 0; i < 9; i++)
            if(t[i] == 'x') x = i / 3, y = i % 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 top = t;
                swap(t[a * 3 + b],t[x * 3 + y]);
                string state = t;
                if(!check[state])
                {
                    check[state] = true;
                    q.push(state);
                    parent[state] = {op[i], top};
                }
                swap(t[a * 3 + b],t[x * 3 + y]);

            }

        }
    }

    string res = "";
    while(parent[end].first != '0')
    {
        res += parent[end].first;
        end = parent[end].second;
    }
    reverse(res.begin(), res.end());
    return res;
}


int main()
{
    string begin = "";
    string end = "12345678x";
    char ch;
    for(int i = 0; i < 9; i++)
    {
        cin >> ch;
        begin +=ch;
    }


    if(!has_ans(begin)) puts("unsolvable");
    else
    {
      cout << bfs(begin) << endl;
    }

    return 0;
}

A*算法

#include <bits/stdc++.h>

using namespace std;

int dx[] = {-1, 0, +1, 0}, dy[]={0, +1, 0, -1};
char op[] = {'u', 'r', 'd', 'l'};


unordered_map<string, pair<char, string>> parent;
unordered_map<string, int> dist;
priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> heap;

int f(string state)
{
    int res = 0;
    for(int i = 0; i < 9; i++)
        if(state[i] != 'x')
        {
            int num = state[i] - '1';
            res += abs(i / 3 - num / 3) + abs(i % 3 - num % 3);
        }
    return res;
}

string Astar(string &start)
{
    string end = "12345678x";
    heap.push({f(start), start});
    parent[start] = {'0', "god"};
    dist[start] = 0;

    while(heap.size())
    {
        auto t = heap.top(); heap.pop();
        string top = t.second;

        if(top == end) break;
        int x = 0, y = 0;
        for(int i = 0; i < 9; i++)
            if(top[i] == 'x')
            {
                x = i / 3, y = i % 3;
                break;
            }

        for(int i = 0; i < 4; i++)
        {
            int a = x + dx[i], b = y + dy[i];
            string temp = top;
            if(a >= 0 && a < 3 && b >= 0 && b < 3)
            {
                swap(top[a * 3 + b], top[x * 3 + y]);
                string state = top;

                if(!dist.count(state) || dist[state] > dist[temp]  +1 )
                {
                    dist[state] = dist[temp] + 1;
                    parent[state] = {op[i], temp};
                    heap.push({dist[state] + f(state), state});
                }
                swap(top[a * 3 + b], top[x * 3 + y]);
            }
        }
    }



    string res = "";

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

    return res;
}

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

    int has_ans = 0;

    for(int i = 0; i < 9; i++)
        for(int j = i; j < 9; j++)
            if(begin[i] != 'x' && begin[j] !='x' && begin[i] > begin[j]) has_ans++;
    if(has_ans % 2 == 0)
    {
        cout << Astar(begin) << endl;
    }
    else puts("unsolvable");

    return 0;
}