675.md

675 Cut Off Trees for Golf Event

Description

link

---

General Type

A* 寻路算法

---

General Solution

A* 算法的本质是用来寻路，上面那篇blog讲的非常详细，简单总结

发展历程：BFS -> Dijkstra -> Greedy BFS -> A*

Core：

• 使用两个list，其中openlist是当前需要遍历的节点，而closelist是已经遍历完成的节点
• openlist在不同情况下是不同优先队列，以F(N)为优先级
• F(N)=G(N)+H(N)
• G(N)就是从起点到当前节点N的移动消耗
• H(N)，在只允许上下左右移动的前提下，就是最好优先贪婪算法中当前节点N到目标节点E的曼哈顿距离

算法流程：

1. 选择起始节点S和目标节点E，将(S,0)（节点，节点F(N)值）放入openList，openList是一个优先队列，节点F(N)值越小，优先级越高。
2. 判断openList是否为空，若为空，则搜索失败，目标节点不可达；否则，取出openList中优先级最高的节点P;
3. 遍历P的上下左右四个相邻接点N1-N4，对每个节点N，如果N已经在closeList中，忽略；否则有两种情况，
   1. 如果N不在openList中，令GN=GP+DPN，计算N到E的曼哈顿距离HN，令FN=GN+HN，令N的父节点为P，将(N,FN)放入openList；
   2. 如果N已经在openList中，计算GN1= GP+DPN，如果GN1小于GN，那么用新的GN1替换GN，重新计算FN，用新的(N,FN)替换openList中旧的(N,FN)，令N的父节点为P；如果GN1不小于GN，不作处理。
4. 将节点P放入closeList中。判断节点P是不是目标节点E，如果是，搜索成功，获取节点P的父节点，并递归这一过程（继续获得父节点的父节点），直至找到初始节点S，从而获得从P到S的一条路径；否则，重复步骤2;

Solution

• Explanation

Distance（） 求解Tree到下一个Tree的距离，如果使用BFS会浪费大量时间在全图扫描上，所以这里使用一种取巧的办法

• 首先判断是否所有的tree都可以遍历到，不能的话返回-1
• 当前now数组保存所有靠近目标的节点，closer
• soon数组保存所有需要绕路的节点
• 每当now遍历完而没有达到目标时，替换soon为now，此时因为soon当中都是多绕了一次路的，所以计算结果需要加上2

为什么可以节约时间在于每次先从最优解开始求起而不是遍历全图，就算是存在绕路也接近最优解

---

Code

class Solution:
    def cutOffTree(self, forest: List[List[int]]) -> int:
        # Add sentinels (a border of zeros) so we don't need index-checks later on.
        forest.append([0] * len(forest[0]))
        for row in forest:
            row.append(0)

        # Find the trees.
        trees = [(height, i, j)
                 for i, row in enumerate(forest)
                 for j, height in enumerate(row)
                 if height > 1]

        # Can we reach every tree? If not, return -1 right away.
        queue = [(0, 0)]
        reached = set()
        for i, j in queue:
            if (i, j) not in reached and forest[i][j]:
                reached.add((i, j))
                queue += (i+1, j), (i-1, j), (i, j+1), (i, j-1)
        if not all((i, j) in reached for (_, i, j) in trees):
            return -1

        # Distance from (i, j) to (I, J).
        def distance(i, j, I, J):
            now, soon = [(i, j)], []
            expanded = set()
            manhattan = abs(i - I) + abs(j - J)
            detours = 0
            while True:
                if not now:
                    now, soon = soon, []
                    detours += 1
                i, j = now.pop()
                if (i, j) == (I, J):
                    return manhattan + 2 * detours
                if (i, j) not in expanded:
                    expanded.add((i, j))
                    for i, j, closer in (i+1, j, i < I), (i-1, j, i > I), (i, j+1, j < J), (i, j-1, j > J):
                        if forest[i][j]:
                            (now if closer else soon).append((i, j))

        # Sum the distances from one tree to the next (sorted by height).
        trees.sort()
        return sum(distance(i, j, I, J) for (_, i, j), (_, I, J) in zip([(0, 0, 0)] + trees, trees))