C++ 启发式搜索 – 优先队列priority_queue

广搜会四面八方搜索很多无用路径，用启发式搜索解决只向目标方向进行搜索，避免四面八方搜索

• 实现：1）起点开始搜索。 2）预估到终点的距离

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

char mmap[105][105]; //地图大小
int cnt, //记录目前为止搜过了多少个点
n, m, //地图大小
sx, sy, //起点坐标
ex, ey, //终点坐标
mark[105][105][2], //去重 记录路径
dir[8][2] = { 0, 1, 1, 0, 0, -1, -1, 0, 1, 1, 1, -1, -1, 1, -1, -1 }; //方向数组

struct node {
    int x, y, step; //step : 到坐标(x,y)需要走几步
    double dis; //预估起点到终点的距离
    bool operator< (const node& b) const { //优先队列默认大顶堆，重载<实现小顶堆
        return this->step + this->dis > b.step + b.dis; //起点距离+预估距离：和越小越出优先队列
    }
};

void func(int x, int y) {
    if (mmap[x][y] == 'S') return; //结束条件：递归到了起点
    mmap[x][y] = 'o';
    func(mark[x][y][0], mark[x][y][1]); //改父节点
}

void print() {
    cout << "############## cnt = " << cnt << "##################" << endl;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cout << mmap[i][j];
            if (mmap[i][j] == 'x')
                mmap[i][j] = '*'; //* : 表示之前已经搜索过此点
        }
        cout << endl;
    }
    cout << "@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@" << endl;
}

double cal_dis(int x, int y) { //计算到终点的直线距离
    return sqrt((ex - x) * (ex - x) + (ey - y) * (ey - y));
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            cin >> mmap[i][j];
            (mmap[i][j] == 'S') && (sx = i) && (sy = j);
            (mmap[i][j] == 'T') && (ex = i) && (ey = j);
        }
    priority_queue<node> que;
    que.push({sx, sy, 0, cal_dis(sx, sy) }); //压入起点
    while (!que.empty()) {
        node tmp = que.top();
        que.pop();
        for (int i = 0; i < 8; ++i) {
            int x = tmp.x + dir[i][0],
                y = tmp.y + dir[i][1]; //新点坐标
            if (mmap[x][y] == 'T') { //走到了终点
                func(tmp.x, tmp.y); //打印走过的路径
                print();
                cout << ++tmp.step << endl;
                return 0;
            }
            if (mmap[x][y] == '.') { //表示可以走的路径
                que.push({x, y, tmp.step + 1, cal_dis(x, y)});
                mmap[x][y] = 'x'; //去重
                mark[x][y][0] = tmp.x; //横坐标从tmp.x来的
                mark[x][y][1] = tmp.y; //纵坐标从tmp.y来的
                ++cnt;
                if (cnt % 10 == 0) print();
            }
        }
    }
    cout << "cant not via the end " << endl;
    return 0;
}