力扣链接：752. 打开转盘锁 ，难度：中等。
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 9 变为 0，0 变为 9 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。
输入: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出: 6
解释:
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。
输入: deadends = ["8888"], target = "0009"
输出: 1
解释: 把最后一位反向旋转一次即可 "0000" -> "0009"。
输入: ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出: -1
解释: 无法旋转到目标数字且不被锁定。
1 <= deadends.length <= 500deadends[i].length == 4target.length == 4target不在deadends之中target和deadends[i]仅由若干位数字组成
提示 1
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`.我们可以把这个问题想像为一个求无向图的最短路径问题。
图中最多有10000个顶点，从顶点'0000'到顶点'9999'，但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 numberof something of a graph,Breadth-First Searchwould probably help. -
Breadth-First Searchemphasizes first-in-first-out, so a queue is needed.
重头戏来了！
A* (A-Star) 算法 可以用于极大提升 广度优先搜索 的性能。
广度优先搜索 对每一个顶点都同等对待，这样难免性能会差。
A* (A-Star) 算法 会对每一个顶点与目标顶点的距离进行计算，距离近的顶点优先处理，相当于为下一步处理哪个顶点指明了方向，因此性能有很大的提升！
A* (A-Star) 算法 和 Dijkstra's 算法 比较像，但A* 算法的目标顶点是明确的，但Dijkstra's 算法不明确。Dijkstra's 算法是走到哪个顶点就计算从起点到那个顶点的距离。
- 要用
priority_queue。 - 计算距离的
启发式函数要精心设计。设计不好，将导致不易察觉的结果错误! - 在特殊情况下，单纯地用
距离作为priority_queue的排序依据还不够，还要调整一下（比如与步数变量值相加），以使最后几步能精确（本例子不涉及，但这个例子 1197. Minimum Knight Moves 涉及）。
N是deadends.length.
- 时间:
O(10^4). - 空间:
O(N).
- 时间:
O(5 * 4 * 4 * 2 + N). - 空间:
O(N).
class Solution:
def openLock(self, deadends: List[str], target_digits: str) -> int:
if '0000' == target_digits:
return 0
self.deadends = set(deadends)
if '0000' in deadends:
return -1
self.queue = deque(['0000'])
self.deadends.add('0000')
self.target_digits = target_digits
result = 0
while self.queue:
result += 1
queue_size = len(self.queue)
for _ in range(queue_size):
digits = self.queue.popleft()
if self.turn_one_slot(digits):
return result
return -1
def turn_one_slot(self, digits):
for i in range(len(digits)):
for digit in closest_digits(int(digits[i])):
new_digits = f'{digits[:i]}{digit}{digits[i + 1:]}'
if new_digits == self.target_digits:
return True
if new_digits in self.deadends:
continue
self.queue.append(new_digits)
self.deadends.add(new_digits)
def closest_digits(digit):
if digit == 0:
return (9, 1)
if digit == 9:
return (8, 0)
return (digit - 1, digit + 1)class Solution:
def openLock(self, deadends: List[str], target_digits: str) -> int:
if '0000' == target_digits:
return 0
deadends = set(deadends)
if '0000' in deadends:
return -1
self.target_digits = target_digits
priority_queue = [(self.distance('0000'), '0000', 0)]
while priority_queue:
_, digits, turns = heapq.heappop(priority_queue)
for i in range(4):
for digit in closest_digits(int(digits[i])):
new_digits = f'{digits[:i]}{digit}{digits[i + 1:]}'
if new_digits == target_digits:
return turns + 1
if new_digits in deadends:
continue
heapq.heappush(
priority_queue,
(self.distance(new_digits), new_digits, turns + 1)
)
deadends.add(new_digits)
return -1
def distance(self, digits):
result = 0
# 0 1 2 3 4 5 6 7 8 9
# 0 1 2 3 4 5 6 7 8 9
# 0 1 2 3 4 5 6 7 8 9
# 0 1 2 3 4 5 6 7 8 9
for i in range(4):
# 'Euclidean Distance' is widely used in 'A* Algorithm'.
result += abs(int(self.target_digits[i]) - int(digits[i])) ** 2
return result ** 0.5
def closest_digits(digit):
if digit == 0:
return (9, 1)
if digit == 9:
return (8, 0)
return (digit - 1, digit + 1)// Welcome to create a PR to complete the code of this language, thanks!// Welcome to create a PR to complete the code of this language, thanks!// Welcome to create a PR to complete the code of this language, thanks!// Welcome to create a PR to complete the code of this language, thanks!// Welcome to create a PR to complete the code of this language, thanks!# Welcome to create a PR to complete the code of this language, thanks!// Welcome to create a PR to complete the code of this language, thanks!