# You have a lock in front of you with 4 circular wheels. Each wheel has 10 slot
# s: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freel
# y 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 i
# t is impossible. 
# 
#  
#  Example 1: 
# 
#  
# Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
# Output: 6
# Explanation:
# A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "12
# 01" -> "1202" -> "0202".
# Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would
#  be invalid,
# because the wheels of the lock become stuck after the display becomes the dead
#  end "0102".
#  
# 
#  Example 2: 
# 
#  
# Input: deadends = ["8888"], target = "0009"
# Output: 1
# Explanation:
# We can turn the last wheel in reverse to move from "0000" -> "0009".
#  
# 
#  Example 3: 
# 
#  
# Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], t
# arget = "8888"
# Output: -1
# Explanation:
# We can't reach the target without getting stuck.
#  
# 
#  Example 4: 
# 
#  
# Input: deadends = ["0000"], target = "8888"
# Output: -1
#  
# 
#  
#  Constraints: 
# 
#  
#  1 <= deadends.length <= 500 
#  deadends[i].length == 4 
#  target.length == 4 
#  target will not be in the list deadends. 
#  target and deadends[i] consist of digits only. 
#  
#  Related Topics 广度优先搜索 
#  👍 245 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
# import collections
# from typing import List


class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        if '0000' in deadends or target in deadends:
            return -1

        def up(ori, idx):
            new = ori[:]
            new[idx] = (ori[idx] + 1) if ori[idx] != 9 else 0
            return new

        def down(ori, idx):
            new = ori[:]
            new[idx] = (ori[idx] - 1) if ori[idx] != 0 else 9
            return new

        target = [int(i) for i in target]
        queue = collections.deque([[0, 0, 0, 0]])
        cnt = 0
        visited = {'0000'}
        visited.update(deadends)
        while queue:
            for _ in range(len(queue)):
                node = queue.popleft()
                if node == target:
                    return cnt

                for i in range(4):
                    for action in (up, down):
                        new_value = action(node, i)
                        new_value_str = ''.join(map(str, new_value))
                        if new_value_str not in visited:
                            visited.add(new_value_str)
                            queue.append(new_value)
            cnt += 1
        return -1


# leetcode submit region end(Prohibit modification and deletion)
# if __name__ == '__main__':
#     print(Solution().openLock(["0201","0101","0102","1212","2002"], '0202'))
