LeetCode link:[752. Open the Lock](https://leetcode.com/problems/open-the-lock), difficulty:**Medium**.

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots:`'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'`. The wheels can rotate freely and wrap around: for example we can turn`9` to be`0`, or`0` to be`9`. Each move consists of turning one wheel one slot.

The lock initially starts at`0000`, a string representing the state of the 4 wheels.

You are given a list of`deadends` dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a`target` representing the value of the wheels that will unlock the lock, return_the**minimum total number** of turns required to open the lock, or`-1` if it is impossible_.

**Input**:`deadends = ["0201","0101","0102","1212","2002"], target = "0202"`

**Output**:`6`

**Explanation**:

**Input**:`deadends = ["8888"], target = "0009"`

**Output**:`1`

**Explanation**:

**Input**:`["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"`

**Output**:`-1`

**Explanation**:`We cannot reach the target without getting stuck.`

-`target`**will not be** in the list`deadends`.

-`target` and`deadends[i]` consist of digits only.

<details>

<summary>Hint 1</summary>

We can think of this problem as a shortest path problem on a graph: there are`10000` nodes (strings`'0000'` to`'9999'`), and there is an edge between two nodes if they differ in one digit, that digit differs by 1 (wrapping around, so`'0'` and`'9'` differ by 1), and if*both* nodes are not in`deadends`.

</details>

We can think of this problem as a shortest path problem on a graph: there are`10000` nodes (strings`'0000'` to`'9999'`), and there is an edge between two nodes if they differ in one digit, that digit differs by 1 (wrapping around, so`'0'` and`'9'` differ by 1), and if*both* nodes are not in`deadends`.

* As shown in the figure above,**Breadth-First Search** can be thought of as visiting vertices in rounds and rounds. Actually, whenever you see a question is about

getting`minimum number` of something of a graph,`Breadth-First Search` would probably help.

*`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.

**A-Star Algorithm** calculates the**distance** between each`vertex` and the`target vertex`, and prioritizes vertices with close distances, which greatly improves performance.

1. Use`priority_queue`.

2. The function 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 for`priority_queue` is not enough, and you need to**make some adjustments**, such as adding it to the`step_count` variable value (not involved in this example).

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

* Space:`O(N)`.

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

* Space:`O(N)`.

classSolution:

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

if'0000'== target_digits:

self.deadends=set(deadends)

if'0000'in deadends:

self.queue= deque(['0000'])

self.deadends.add('0000')

self.target_digits= target_digits

result=0

whileself.queue:

result+=1

queue_size=len(self.queue)

for _inrange(queue_size):

digits=self.queue.popleft()

ifself.turn_one_slot(digits):

return result

defturn_one_slot(self,digits):

for iinrange(len(digits)):

for digitin closest_digits(int(digits[i])):

new_digits=f'{digits[:i]}{digit}{digits[i+1:]}'

if new_digits==self.target_digits:

if new_digitsinself.deadends:

self.queue.append(new_digits)

self.deadends.add(new_digits)

defclosest_digits(digit):

if digit==0:

return (9,1)

if digit==9:

return (8,0)

return (digit-1, digit+1)

classSolution:

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

if'0000'== target_digits:

deadends=set(deadends)

if'0000'in deadends:

self.target_digits= target_digits

priority_queue= [(self.distance('0000'),'0000',0)]

while priority_queue:

_, digits, turns= heapq.heappop(priority_queue)

for iinrange(4):

for digitin closest_digits(int(digits[i])):

new_digits=f'{digits[:i]}{digit}{digits[i+1:]}'

if new_digits== target_digits:

return turns+1

if new_digitsin deadends:

heapq.heappush(

priority_queue,

(self.distance(new_digits), new_digits, turns+1)

)

deadends.add(new_digits)

defdistance(self,digits):

result=0

for iinrange(4):

result+=abs(int(self.target_digits[i])-int(digits[i]))**2

return result**0.5

defclosest_digits(digit):

if digit==0:

return (9,1)

if digit==9:

return (8,0)

return (digit-1, digit+1)