A* 曼哈顿距离

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>

using namespace std;

const int N = 104;

typedef pair<int, int> PII;

PII direction[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

int n, m;
int maze[N][N];
int dis[N][N];

PII operator+(const PII& a, const PII& b) {
    return {a.first + b.first, a.second + b.second};
}

struct Man {                // 曼哈顿距离
    int x, y;
    Man(int x_, int y_) : x(x_), y(y_) {}
    bool operator()(const PII& a, const PII& b) {
        int ga = dis[a.first][a.second];
        int gb = dis[b.first][b.second];
        int ha = abs(a.first - x) + abs(a.second - y);
        int hb = abs(b.first - x) + abs(b.second - y);
        return (ga + ha) > (gb + hb); // 优先较小
    }
};

void bfs() {
    priority_queue<PII, vector<PII>, Man> pq(Man(n, m));
    pq.push({1, 1});
    dis[1][1] = 0;

    while (!pq.empty()) {
        PII h = pq.top();
        pq.pop();

        if (h.first == n && h.second == m) return; 

        for (PII dir : direction) {
            PII p = h + dir;
            if (p.first > 0 && p.second > 0 && p.first <= n && p.second <= m && maze[p.first][p.second] == 0) {
                int new_dist = dis[h.first][h.second] + 1;
                if (dis[p.first][p.second] == -1 || new_dist < dis[p.first][p.second]) {
                    dis[p.first][p.second] = new_dist;
                    pq.push(p);
                }
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 1; j <= m; j ++) 
            cin >> maze[i][j];
    for (int i = 0; i <= n+1; i ++ )
        for (int j = 0; j <= m+1; j++)
            dis[i][j] = -1;
    bfs();
    cout << dis[n][m];
}