C++A星寻路代码

以下是一个简单的C++ A星寻路代码实现：

#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;

const int INF = 1e9; // 无穷大
const int MAXN = 1005; // 最大节点数

struct Node {
    int x, y; // 坐标
    int g, h; // 距离起点的代价g和距离终点的代价h
    int f() const { // 总代价f
        return g + h;
    }
};

int n, m; // 地图大小
char map[MAXN][MAXN]; // 地图
Node start, end; // 起点和终点
int vis[MAXN][MAXN]; // 是否访问过

// 估算距离函数，这里取曼哈顿距离
int estimate(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}

// A*搜索函数
int astar() {
    priority_queue<pair<int, Node>> Q; // 优先队列
    Q.push(make_pair(0, start));
    while (!Q.empty()) {
        Node u = Q.top().second;
        Q.pop();
        if (u.x == end.x && u.y == end.y) { // 找到终点
            return u.g;
        }
        if (vis[u.x][u.y]) { // 已经访问过，跳过
            continue;
        }
        vis[u.x][u.y] = 1; // 标记为已访问
        // 枚举相邻节点
        for (int dx = -1; dx <= 1; dx++) {
            for (int dy = -1; dy <= 1; dy++) {
                if (dx == 0 && dy == 0) {
                    continue;
                }
                int nx = u.x + dx, ny = u.y + dy;
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                    continue; // 超出边界
                }
                if (map[nx][ny] == '#') {
                    continue; // 障碍物
                }
                Node v = {nx, ny, u.g + 1, estimate(nx, ny, end.x, end.y)};
                Q.push(make_pair(-v.f(), v)); // 插入队列，优先级为f的相反数
            }
        }
    }
    return -1; // 没有找到路径
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> map[i];
        for (int j = 0; j < m; j++) {
            if (map[i][j] == 'S') {
                start = {i, j, 0, 0};
            }
            if (map[i][j] == 'E') {
                end = {i, j, 0, 0};
            }
        }
    }
    int ans = astar();
    if (ans == -1) {
        cout << "No path found." << endl;
    } else {
        cout << "The shortest path is " << ans << "." << endl;
    }
    return 0;
}

该代码实现了一个简单的A星寻路算法，包括估算距离函数、A星搜索函数和主函数。其中使用了STL的priority_queue来实现优先队列。