A* 求16宫格拼图

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

using namespace std;

#define N 4
#define N2 16
#define LIMIT 100

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'};
int MDT[N2][N2];

struct Puzzle
{
    int f[N2];                  //16个位置
    int space;                  //空格的位置
    int MD;
    int cost;

    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];
        }
    }

};

struct State
{
    Puzzle puzzle;
    int estimated;
    bool operator <(const State &s) const           //优先队列中按照需求的最低排序，每次取出需求最低的状态进行转移
    {
        return estimated > s.estimated;
    }
};

int getAllMD(Puzzle pz)
{
    int sum = 0;
    for(int i = 0; i < N2; i++)
    {
        if(pz.f[i] == N2)
            continue;
        sum += MDT[i][pz.f[i]-1];
    }

    return sum;
}


int astar(Puzzle s)
{
    priority_queue<State> PQ;

    s.MD = getAllMD(s);
    s.cost = 0;
    map<Puzzle, bool> V;
    Puzzle u, v;
    State initial;
    initial.puzzle = s;
    initial.estimated = getAllMD(s);
    PQ.push(initial);

    while(!PQ.empty())
    {
        State st = PQ.top();
        PQ.pop();
        u = st.puzzle;

        if(u.MD == 0)
            return u.cost;
        V[u] = true;

        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.MD -= MDT[tx*N+ty][v.f[tx*N+ty] - 1];
            v.MD += MDT[sx*N+sy][v.f[tx*N+ty] - 1];

            swap(v.f[sx*N+sy], v.f[tx*N+ty]);
            v.space = tx*N+ty;

            if(!V[v])
            {
                v.cost++;                                            //花费每次加一
                State news;
                news.puzzle = v;
                news.estimated = v.cost + v.MD;                     //需求等于花费加曼哈顿距离
                PQ.push(news);
            }

        }
    }

    return -1;
}

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

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

    for(int i = 0; i < N2; i++)
    {
        for(int j = 0; j < N2; j++)
        {
            MDT[i][j] = abs(i/N-j/N) + abs(i%N-j%N);
        }
    }

    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;
        }
    }

    cout << astar(in) << endl;

    return a.exec();
}