cpp A* 路网数据寻路

A*算法是一种基于启发式搜索的寻路算法，可以在路网数据中寻找最短路径。下面是一个简单的C++实现，假设路网数据是一个二维数组，0表示可以通行，1表示不可通行。

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

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

int n, m; // 路网数据的行列数
int sx, sy, ex, ey; // 起点和终点的坐标
int map[MAXN][MAXN]; // 路网数据
int dis[MAXN][MAXN]; // 距离起点的距离
bool vis[MAXN][MAXN]; // 是否已经访问过
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}; // 方向数组

struct Node {
    int x, y, f, g, h; // 坐标、f值、g值、h值
    bool operator<(const Node& a) const {
        return f > a.f; // 优先队列为小根堆，f值小的优先级高
    }
};

int heuristic(int x, int y) {
    // 启发函数，计算当前节点到终点的估价函数值
    return abs(x - ex) + abs(y - ey);
}

void Astar() {
    // 初始化
    memset(dis, INF, sizeof(dis));
    memset(vis, false, sizeof(vis));
    priority_queue<Node> pq;
    dis[sx][sy] = 0;
    pq.push({sx, sy, 0, 0, heuristic(sx, sy)});
    // A*算法主循环
    while (!pq.empty()) {
        Node u = pq.top(); pq.pop();
        int x = u.x, y = u.y;
        if (vis[x][y]) continue;
        vis[x][y] = true;
        if (x == ex && y == ey) return; // 找到终点，退出
        for (int i = 0; i < 4; i++) {
            int nx = x + dir[i][0], ny = y + dir[i][1];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny] && map[nx][ny] == 0) {
                int g = dis[x][y] + 1; // g值为当前节点到起点的距离
                if (g < dis[nx][ny]) { // 如果新路径更短，则更新距离和f值，并加入队列
                    dis[nx][ny] = g;
                    int h = heuristic(nx, ny);
                    pq.push({nx, ny, g + h, g, h});
                }
            }
        }
    }
}

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

这段代码实现了A*算法的基本框架，包括启发函数的设计、状态的表示、状态转移和优先队列的使用。需要注意的是，A*算法在最坏情况下的时间复杂度为指数级别，因此对于较大的路网数据可能需要使用其他更高效的寻路算法。