a*算法的c++实现

A*算法是一种启发式搜索算法，用于在图形平面上找到从起点到终点的最佳路径。它使用估价函数来评估哪些节点最有可能导致找到最佳解决方案，从而使搜索更加高效。以下是A*算法的C++实现：

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAXN = 1005;
const int INF = 0x3f3f3f3f;

int n, m, sx, sy, ex, ey;
int map[MAXN][MAXN];
int dis[MAXN][MAXN];
bool vis[MAXN][MAXN];

struct Node {
    int x, y, f;
    bool operator < (const Node &a) const {
        return f > a.f;
    }
};

int A_star() {
    memset(dis, INF, sizeof(dis));
    memset(vis, false, sizeof(vis));
    priority_queue<Node> q;
    q.push({sx, sy, 0});
    dis[sx][sy] = 0;
    while (!.empty()) {
        Node u = q.top();
        q.pop();
        if (vis[u.x][u.y]) continue;
        vis[u.x][u.y] = true;
        if (u.x == ex && u.y == ey) return dis[ex][ey];
        int dx[4] = {0, 0, 1, -1};
        int dy[4] = {1, -1, 0, 0};
        for (int i = 0; i < 4; i++) {
            int nx = u.x + dx[i];
            int ny = u.y + dy[i];
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
            if (map[nx][ny] == -1) continue;
            if (dis[nx][ny] > dis[u.x][u.y] + map[nx][ny]) {
                dis[nx][ny] = dis[u.x][u.y] + map[nx][ny];
                q.push({nx, ny, dis[nx][ny] + abs(nx - ex) + abs(ny - ey)});
            }
        }
    }
    return -1;
}

int main() {
    cin >> n >> m >> sx >> sy >> ex >> ey;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> map[i][j];
        }
    }
    int ans = A_star();
    cout << ans << endl;
    return 0;
}