九宫格拼图问题（BFS）

#include <bits/stdc++.h>
using namespace std;
#define N 3
#define N2 9
const int dx[] = {0, 0, -1, 1}; //分别对应上下左右移动
const int dy[] = {1, -1, 0, 0};
const string pth[] = {"u", "d", "l", "r"};

struct node
{
    string path = "";
    int f[N2];
    int space; //空格所在位置

    bool operator<(const node &p)const
    {
        for(int i=0;i<N2;++i)
        {
            if(f[i]==p.f[i])
                continue;
            return f[i]<p.f[i];
        }
        return false;
    }
};

bool is_target(node nd)
{
    for (int i = 0; i < 9; ++i)
    {
        if (nd.f[i] != i + 1)
            return false;
    }
    return true;
}

string bfs(node st)
{
    queue<node> Q;
    map<node, bool> mp;

    st.path = "";
    Q.push(st);
    mp[st] = true;
    node u, v;

    while (!Q.empty())
    {
        u = Q.front();
        Q.pop();

        if (is_target(u))
            return u.path;

        int sx = u.space / N;
        int sy = u.space % N;

        for (int i = 0; i < 4; ++i)
        {
            int tx = sx + dx[i];
            int ty = sy + dy[i];
            if (tx >= N || tx < 0 || ty >= N || ty < 0)
                continue;
            v = u;
            v.path += pth[i];
            swap(v.f[u.space], v.f[N * tx + ty]);
            v.space = N * tx + ty;

            if(!mp[v])
            {
                //确保没有存在过这条路径
                mp[v] = true;
                Q.push(v);
            }
        }
    }

    return "cannot_solve";
}

int main()
{
    node st;
    for (int i = 0; i < N2; ++i)
    {
        cin >> st.f[i];
        if (st.f[i] == 0)
        {
            st.space = i;
            st.f[i] = N2;
        }
    }
    string ans = bfs(st);
    if(ans!="cannot_solve")
        cout<<ans.length()<<endl;
}