【题解】A*算法求解迷宫最短路径

题目描述

给定一个 n × m 迷宫，每步可以向上、下、左、右移动一格，但不能移动到障碍格子上，求从起点到终点的最短路径。

输入格式

第一行包含起点坐标 x1, y1 和终点坐标 x2, y2。

第二行包含两个整数 n 和 m。

接下来 n 行，每行包含 m 个整数，用来表示整个迷宫。

其中，0 表示空地，1 表示障碍。

输出格式

输出一个整数，表示起点到终点的最短路径长度。

如果不存在最短路径，则输出 −1。

数据范围

$ 1 n,m ^5 \(，\) 1 x_1,x_2 n \(，\) 1 y_1,y_2 m $

输入样例：

1 1 3 3
3 3
0 0 0
0 1 0
0 0 0

输出样例：

4

题解

A*算法

A*算法是一种启发式搜索算法，它在BFS的基础上，引入了一个启发函数，用于评估当前节点到终点的距离，从而在搜索过程中，优先搜索距离终点更近的节点。

其实只需要在Dijkstra算法的基础上，将优先队列的比较函数改为：

bool operator<(const pqnode& another) const {
    if (mode == DIJKSTRA)
        return cost > another.cost;
    else if (mode == A_STAR)
        return cost + abs(target.x - x) + abs(target.y - y) >
                another.cost + abs(target.x - another.x) + abs(target.y - another.y);
    else
        throw "Invalid mode";
}

即可实现A*算法。