자물쇠 열기

당신 앞에는 4개의 원형 바퀴가 있는 자물쇠가 있습니다. 각 바퀴에는 10개의 슬롯이 있습니다: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' . 바퀴는 자유롭게 회전하고 감을 수 있습니다. 예를 들어 '9'를 '0'로 돌리거나 '0'를 '9'로 돌릴 수 있습니다. 각 이동은 하나의 휠을 하나의 슬롯으로 돌리는 것으로 구성됩니다.

잠금은 처음에 4개의 바퀴의 상태를 나타내는 문자열인 '0000' 에서 시작됩니다.
deadends 막다른 골목 목록이 제공됩니다. 즉, 자물쇠에 이러한 코드가 표시되면 자물쇠의 바퀴가 회전을 멈추고 열 수 없게 됩니다.

자물쇠를 여는 바퀴의 값을 나타내는 target가 주어지면 자물쇠를 여는 데 필요한 최소 총 회전 수를 반환하거나 불가능할 경우 -1을 반환합니다.

예 1:

입력: deadends = ["0201","0101","0102","1212","2002"], 대상 = "0202"
출력: 6
설명:
유효한 동작의 순서는 "0000"-> "1000"-> "1100"-> "1200"-> "1201"-> "1202"-> "0202"입니다.
"0000"-> "0001"-> "0002"-> "0102"-> "0202"와 같은 시퀀스는 유효하지 않습니다.
디스플레이가 "0102"막다른 골목이 된 후 자물쇠의 바퀴가 끼이기 때문입니다.

예 2:

입력: deadends = ["8888"], 대상 = "0009"
출력: 1
설명: 마지막 바퀴를 반대로 돌려 "0000"-> "0009"로 이동할 수 있습니다.

예 3:

입력: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], 대상 = "8888"
출력: -1
설명: 막히지 않고는 목표에 도달할 수 없습니다.

제약:

1 <= deadends.length <= 500

deadends[i].length == 4

target.length == 4

대상이 목록에 없습니다deadends.

target 및 deadends[i]는 숫자로만 구성됩니다.

해결책:

class Solution:
    def getSteps(self, curr):
        steps = set()
        for i in range(4):
            for d in [1, -1]:
                now = list(curr)
                now[i] = (10 + now[i] + d) % 10
                steps.add(tuple(now))
        return steps

    def openLock(self, deadends: List[str], target: str) -> int:
        beg = (0, 0, 0, 0)
        target = tuple(int(d) for d in target)
        paths = [(beg, 0)]
        visited = {beg}
        for end in deadends:
            end = tuple(int(d) for d in end)
            if beg == end:
                return -1
            visited.add(end)
        i = 0
        while i < len(paths):
            curr, steps = paths[i]
            if curr == target:
                return steps
            for j in self.getSteps(curr):
                if j not in visited:
                    visited.add(j)
                    paths.append((j, steps + 1))
            i += 1
        return -1