启发式搜索迷宫问题C++

以下是使用C++实现启发式搜索算法解决迷宫问题的示例代码：

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

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

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

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

int heuristic(int x, int y) {
    return abs(x - ex) + abs(y - ey);
}

void A_star() {
    priority_queue<Node> q;
    q.push({sx, sy, heuristic(sx, sy)});
    dis[sx][sy] = 0;
    while (!q.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;
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                if (i == 0 && j == 0) continue;
                int nx = u.x + i, ny = u.y + j;
                if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
                if (maze[nx][ny] == 1) continue;
                if (dis[nx][ny] > dis[u.x][u.y] + 1) {
                    dis[nx][ny] = dis[u.x][u.y] + 1;
                    q.push({nx, ny, dis[nx][ny] + heuristic(nx, ny)});
                }
            }
        }
    }
}

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

该算法使用了A*算法，其中heuristic函数用于计算当前节点到终点的估价函数值，优先队列q用于存储待扩展的节点，dis数组用于记录起点到每个节点的最短距离，vis数组用于记录每个节点是否已经被访问过。在A_star函数中，首先将起点加入优先队列q中，然后不断从队列中取出f值最小的节点进行扩展，直到找到终点或者队列为空。在扩展节点时，对于每个相邻节点，如果该节点未被访问过且可以到达，则更新该节点的最短距离，并将该节点加入优先队列q中。