752. 打开转盘锁

Difficulty
Medium
Tags
BFS
URL
https://leetcode-cn.com/problems/open-the-lock/
Star
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。
示例 1:
输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。
示例 2:
输入: deadends = ["8888"], target = "0009"
输出：1
解释：
把最后一位反向旋转一次即可 "0000" -> "0009"。
示例 3:
输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出：-1
解释：
无法旋转到目标数字且不被锁定。
示例 4:
输入: deadends = ["0000"], target = "8888"
输出：-1
提示：
  • 1 <= deadends.length <= 500
  • deadends[i].length == 4
  • target.length == 4
  • target 不在 deadends 之中
  • target 和 deadends[i] 仅由若干位数字组成

法1 BFS

思路
朴素的宽度优先搜索。
其实等价于计算这颗多叉树的深度,只要相同了这一点，就很好解决了。
当然还是有些许技巧，比如剪枝，开一个集合，不将查验过的节点放入队列。
notion imagenotion image
题解
class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
				# 初始res = -1
        res = -1
        deadends = set(deadends)
        if target in deadends or "0000" in deadends:
            return res

        queue = []
        queue.append("0000")
        visited = set()
        visited.add("0000")

        while queue:
            temp_len = len(queue)
            res += 1
            while temp_len > 0:
                cur_code = queue.pop(0)
                temp_len -= 1

                if cur_code == target:
                    return res

                # 找邻居节点
                for i in range(0, 4):
                    c_1 = str(int(cur_code[i]) + 1) if cur_code[i] != "9" else "0"
                    c_2 = str(int(cur_code[i]) - 1) if cur_code[i] != "0" else "9"
                    for c in [c_1, c_2]:
                        new_code = cur_code[0:i] + c + cur_code[i+1:]
                        if new_code not in deadends and new_code not in visited:
                            visited.add(new_code)
                            queue.append(new_code)

        return -1
优化：双向奔赴版本（双向BFS）
class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        res = -1
        deadends = set(deadends)
        if target in deadends or "0000" in deadends:
            return res
        if target == "0000":
            return 0
            
        begin_queue = set()
        end_queue = set()
        begin_queue.add("0000")
        end_queue.add(target)
        visited = set()
        visited.add("0000")
        visited.add(target)

        while begin_queue and end_queue:
            temp_len = len(begin_queue)
            temp_queue = set()
            res += 1
            while temp_len > 0:
                cur_code = begin_queue.pop()
                temp_len -= 1

                # 找邻居节点
                for i in range(0, 4):
                    c_1 = str(int(cur_code[i]) + 1) if cur_code[i] != "9" else "0"
                    c_2 = str(int(cur_code[i]) - 1) if cur_code[i] != "0" else "9"
                    for c in [c_1, c_2]:
                        new_code = cur_code[0:i] + c + cur_code[i+1:]
                        if new_code not in deadends:
                            if new_code in end_queue:
																# 双向BFS，当前节点的邻居节点在对面，因为是邻居节点，所以得加1
                                return res + 1
                            elif new_code not in visited:
                                visited.add(new_code)
                                temp_queue.add(new_code)

            # 选择小的 作为下一轮的开始，以减小搜索空间
            if len(temp_queue) < len(end_queue):
                begin_queue = temp_queue
            else:
                begin_queue = end_queue
                end_queue = temp_queue

        return -1
class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        visited = set()
        deadends = set(deadends)
        if "0000" in deadends or target in deadends:
            return -1
        if "0000" == target:
            return 0
        res = 0

        begin_queue = set()
        begin_queue.add("0000")
        end_queue = set()
        end_queue.add(target)

        visited.add("0000")
        visited.add(target)

        while begin_queue:
            res += 1
            next_queue = set()
            for cur_code in begin_queue:
                for i in range(0, len(cur_code)):
                    char = int(cur_code[i])
                    up_char = str(char+1) if char != 9 else "0"
                    down_char = str(char-1) if char != 0 else "9"
                    for new_char in [up_char, down_char]:
                        new_code = cur_code[0:i] + new_char + cur_code[i+1:]
													# endqueue 中的肯定不是死亡节点，所以可以直接判断
                        if new_code in end_queue:
                            return res
                        if new_code not in deadends and new_code not in visited:
                            visited.add(new_code)
                            next_queue.add(new_code)

            if len(end_queue) < len(next_queue):
                begin_queue = end_queue
                end_queue = next_queue
            else:
                begin_queue = next_queue

        return -1