概述

AStar算法是用于寻找图的最短路的算法，它是Dijkstra算法的进阶版。Dijkstra算法采用贪心的策略，每次选取能连接到的节点中离起点最近的一个，而AStar算法则不仅考虑某节点到起点的距离，还把节点到终点的距离纳入到评估标准中。当某节点到起点和到终点的距离之和最小时，我们认为该节点最有构成最短路径的潜力，因此选取该节点进行扩展。但是大多数情况下，我们很难知道某节点到终点的距离是多少，所以我们只能估算。在网格图中，我们常使用曼哈顿距离来估算这个值。

曼哈顿距离

A点和B点的曼哈顿距离就是A点沿着格子只能横着或竖着走，到B点的最短距离，它的值是两点的横坐标之差的绝对值加上两点的纵坐标之差的绝对值。例如，在上图中，1 到 6 的曼哈顿距离是 3 , 1 到 5 的曼哈顿距离是 4.

例题

LeetCode 675. 为高尔夫比赛砍树

你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m * n 的矩阵表示，在这个矩阵中：

0 表示障碍，无法触碰
1 表示地面，可以行走
比 1 大的数 表示有树的单元格，可以行走，数值表示树的高度

每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。

你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。

你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。如果你无法砍完所有的树，返回 -1 。

可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。

示例 1：

1
2
3

输入：forest = [[1,2,3],[0,0,4],[7,6,5]]
输出：6
解释：沿着上面的路径，你可以用 6 步，按从最矮到最高的顺序砍掉这些树。

示例 2：

1
2
3

输入：forest = [[1,2,3],[0,0,0],[7,6,5]]
输出：-1
解释：由于中间一行被障碍阻塞，无法访问最下面一行中的树。

示例 3：

输入：forest = [[2,3,4],[0,0,5],[8,7,6]]
输出：6
解释：可以按与示例 1 相同的路径来砍掉所有的树。
(0,0) 位置的树，可以直接砍去，不用算步数。

题解

由于砍树必须按从矮到高砍，我们可以把所有的树排个序，然后依次求相邻的树之间的最短距离，全部加起来就是总的最短距离。相邻的树之间的最短距离就可以用AStar算法查找。

代码：

class Solution {
private:
    vector<int> dist;
    int m;
    int n;
    int f(int start, int end) {
        //计算曼哈顿距离
        int x1 = start / n; int y1 = start % n;
        int x2 = end / n; int y2 = end % n;
        return abs(x1 - x2) + abs(y1 - y2);
    }
    int AStar(int start, int end, vector<vector<int>>& forest) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
        q.push({ f(start,end),start });
        fill(dist.begin(), dist.end(), INT_MAX);
        dist[start] = 0;
        vector<int> dirs = { -1,0,1,0,-1 };
        while (!q.empty()) {
            //每轮从优先队列中弹出到起点和终点距离之和最短的点进行扩展。
            int state = q.top().second;
            q.pop();
            if (state == end) return dist[state];
            for (int i = 0; i < 4; i++) {
                int x = state / n + dirs[i]; int y = state % n + dirs[i + 1];
                if (0 <= x && x<m && 0 <= y && y < n && forest[x][y]>0 && dist[x * n + y]>dist[state] + 1) {
                    /* 如果当前节点已经被查找到过（即已经记录过dist值），
                     * 并且当前计算的到起点的距离比此前查到的距离更短，
                     * 就用当前的距离值代替原来的距离值，并将其放回到优先队列。
                     */
                    dist[x * n + y] = dist[state] + 1;
                    q.push({ dist[x * n + y] + f(x * n + y,end),x * n + y });
                }
            }
        }
        return -1;
    }
public:
    int cutOffTree(vector<vector<int>>& forest) {
        m = forest.size();
        n = forest[0].size();
        dist.resize(m * n);
        vector<pair<int, int>> trees;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (forest[i][j] > 1) {
                    trees.push_back({ forest[i][j],i * n + j });
                }
            }
        }
        sort(trees.begin(), trees.end());
        int start = 0;
        int res = 0;
        for (pair<int, int> tree : trees) {
            int end = tree.second;
            int subdist = AStar(start, end, forest);
            if (subdist == -1) return -1;
            else res += subdist;
            start = end;
        }
        return res;
    }
};

有的没的

在玉泉做核酸拿到了贴纸

贴贴纸真是可爱爱。

环己三烯的冬眠舱

AStar 算法

概述