广度优先搜索求九宫格

#include <QCoreApplication>
#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <stdio.h>

using namespace std;

#define N 3
#define N2 9


struct Puzzle
{
    int f[N2];                  //九个位置
    int space;                  //空格的位置
    string path;                //路径

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

        return false;
    }
};


static const int dx[4] = {-1, 0, 1, 0};
static const int dy[4] = {0, -1, 0, 1};
static const char dir[4] = {'U','L','D','R'};

bool isTarget(Puzzle p)
{
    for(int i = 0; i < N2; i++)
        if(p.f[i] != (i+1))
            return false;

    return true;
}

string bfs(Puzzle s)
{
    queue<Puzzle> Q;
    map<Puzzle, bool> V;

    Puzzle u, v;
    s.path = "";
    Q.push(s);

    V[s] = true;

    while(! Q.empty())
    {
        u = Q.front();
        Q.pop();
        if(isTarget(u))
            return u.path;

        int sx = u.space / N;       //将数组中连续坐标转换为矩阵坐标
        int sy = u.space % N;

        for(int r = 0; r < 4; r++)
        {
            int tx = sx + dx[r];
            int ty = sy + dy[r];

            if(tx < 0 || ty < 0 || tx >= N || ty >= N)
                continue;

            v = u;
            swap(v.f[u.space], v.f[tx*N + ty]);     //下一状态，交换空格位置和目标位置
            v.space = tx*N + ty;                    //将矩阵坐标装换为数组中的位置坐标
            if(!V[v])                               //如果没有记录该状态则加入队列并记录
            {
                V[v] = true;
                v.path += dir[r];
                Q.push(v);
            }
        }
    }

    return "unsolvable";
}


int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);

    freopen("G:\\data.txt", "r", stdin);

    Puzzle in;

    for(int i = 0; i < N2; i++)
    {
        cin >> in.f[i];
        if(in.f[i] == 0)
        {
            in.f[i] = N2;
            in.space = i;
        }
    }

    string ans = bfs(in);

    cout << ans << " " <<  ans.size() << endl;

    return a.exec();
}

/* 1 3 0
 * 4 2 5
 * 7 8 6
 *
 */