*`Breadth-First Search` emphasizes first-in-first-out, so a**queue** is needed.

**A-Star Algorithm** can be used to improve the performance of**Breadth-First Search Algorithm**.

**Breadth-First Search** treats each vertex equally, which inevitably leads to poor performance.

The`A* (A-Star) algorithm` calculates the**distance** between each`vertex` and the`target vertex`, and**prioritizes vertices with closer distances**, which is equivalent to indicating which vertex to process next, so the performance is greatly improved!

The`A* (A-star) search algorithm` calculates the**distance** between each`vertex` and the`target vertex`, and**prioritizes vertices with closer distances**, which is equivalent to indicating which vertex to process next, so the performance is greatly improved!

_A* (A-star) search algorithm_ is similar to_Dijkstra's algorithm_, but the`target vertex` of_A* (A-star) search algorithm_ is clear, while that of_Dijkstra's algorithm_ is not._Dijkstra's algorithm_ calculates the`distance` from the`starting vertex` to the`vertex` it reaches.

1. Use`priority_queue`.

2. The function for calculating`distance` should be**carefully designed** (poor design will lead to**subtle** errors in the results).

2. The**heuristicfunction** for calculating`distance` should be**carefully designed** (poor design will lead to**subtle** errors in the results).

3. In special cases, simply using`distance` as the sorting basis of`priority_queue` is not enough, and it is also necessary to**adjust** (for example, add it to the`number of steps` variable value) to make the last few steps accurate (not involved in this example, yet in this one[1197. Minimum Knight Moves](https://leetcode.com/problems/minimum-knight-moves/)).

* Time:`O(10^4)`.

* Space:`O(N)`.

* Time:`O(5 * 4 * 4 * 2 + N)`.

* Space:`O(N)`.

return (digit-1, digit+1)

classSolution:

defopenLock(self,deadends: List[str],target_digits:str) ->int:

- 1584-min-cost-to-connect-all-points-2.md

- 1514-path-with-maximum-probability.md

- 1334https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance

- 752 a star

1. 要用`priority_queue`。

2.计算距离的函数要**精心设计**。设计不好，将导致不易察觉的结果错误!

2.计算距离的`启发式函数`要**精心设计**。设计不好，将导致不易察觉的结果错误!

3. 在特殊情况下，单纯地用`距离`作为`priority_queue`的排序依据还不够，还要**调整一下**（比如与`步数`变量值相加），以使最后几步能精确（本例子不涉及，但这个例子[1197. Minimum Knight Moves](https://leetcode.com/problems/minimum-knight-moves/) 涉及）。