A*

发布于 2021-01-22  69 次阅读


没有看过任何的代码,完全按照教程里面的思想自己写了一个,感觉可能大概不是这样写的吧()

#include <stdio.h>
#include <queue>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;
#define N 100
bool map[N][N], closelist[N][N];
int path[N][N], G[N][N], F[N][N];
int n, m, stx, sty, edx, edy;
struct Astar
{
    int x, y, G, F;
}openlist[N*N];
struct F
{
    int x, y;
}fa[N][N];
struct cmp
{
    int operator()(Astar a, Astar b)
    {
        return a.F > b.F;
    }
};
int abs(int x)
{
    return x > 0 ? x : -x;
}
int get(int x, int y)
{
    return (abs(x - edx) + abs(y - edy)) * 10;
}
void A_star()
{
    priority_queue<Astar, vector<Astar>, cmp > openlist;
    Astar st = {stx, sty, 0, 0};
    G[stx][sty] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            G[i][j] = 100;
    openlist.push(st);
    closelist[stx][sty] = 1;
    while (!openlist.empty())
    {
        Astar now = openlist.top();
        openlist.pop();
        for (int i = -1; i <= 1; i++)
            for (int j = -1; j <= 1; j++)
                if ((i != 0 || j != 0) && (now.x + i) <= n && (now.x + i) >= 1 && (now.y + j) <= m && (now.y + j) >= 1)
                {
                    if (i != 0 && j != 0 && closelist[now.x + i][now.y +j] != 1 && G[now.x + i][now.y + j] > now.G + 14 && map[now.x + i][now.y + j] != 1 && map[now.x + i][now.y] != 1 && map[now.x][now.y + j] != 1)
                    {
                        Astar next = {now.x + i, now.y + j, now.G + 14,now.G + 14 + get(now.x + i, now.y + j)};
                        closelist[now.x + i][now.y + j] = 1;
                        fa[now.x + i][now. y + j]  = {now.x, now.y};
                        G[now.x + i][now.y + j] = now.G + 14;
                        F[now.x + i][now.y + j] = now.G + 14 + get(now.x + i, now.y + j);
                        if (now.x + i == edx && now.y + j == edy) return;
                        openlist.push(next);

                    }
                    else if ((i == 0 || j == 0) && closelist[now.x + i][now.y +j] != 1 && G[now.x + i][now.y + j] > now.G + 10 && map[now.x + i][now.y + j] != 1)
                    {
                        Astar next = {now.x + i, now.y + j, now.G + 10,now.G + 10 + get(now.x + i, now.y + j)};
                        closelist[now.x + i][now.y + j] = 1;
                        fa[now.x + i][now. y + j]  = {now.x, now.y};
                        G[now.x + i][now.y + j] = now.G + 10;
                        F[now.x + i][now.y + j] = now.G + 14 + get(now.x + i, now.y + j);
                        if (now.x + i == edx && now.y + j == edy) return;
                        openlist.push(next);
                    }
                }
    }
}
int main()
{

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            cin >> map[i][j];
            path[i][j] = map[i][j];
        }
    cin >> stx >> sty >> edx >> edy;
    memset(fa, -1, sizeof(fa));
    A_star();
    int i = edx, j = edy;
    path[i][j] = 4;
    do
    {
        path[fa[i][j].x][fa[i][j].y] = 2;
        int t1 = fa[i][j].x, t2 = fa[i][j].y;
        i = t1;
        j = t2;
    } while (fa[i][j].x != -1);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            cout << path[i][j] << ' ';
        cout << endl;
    }
}

「雪霁融雾月,冰消凝夜雨」