ワイド優先検索、ターンテーブルロックを開く

ターンテーブルロックを開く(Python)
問題を解く構想.
一方的な検索の考え方は、「0000」から出発し、その隣接する組合せを遍歴し、ターゲットではなく、すでにアクセスしたキューに参加し、キューに参加し、次のループが始まるのを待って、後にボタンを受け取る時間がタイムアウトすることです.双方向検索を用いて,ターゲットと「0000」の両方から出発し,どちらの現在のレイヤ集合の検出すべき暗号ロック数が少ないか,どちらを検出する.1つのセットが0の場合、遮断を表し、オンになることはできません.1つのセットの隣人が別のセットに含まれている場合、接続が成功したことを示します.
たんほうこうたんさくけいしき
LeetCode-Python-752. ターンテーブルロックを開く

from collections import deque


class Solution(object):
    def openLock(self, deadends, target):
        """
        :type deadends: List[str]
        :type target: str
        :rtype: int
        """
        deadends = set(deadends)
        if "0000" in deadends:  #           88
            return -1

        queue = deque()
        queue.append(["0000", 0])
        cnt = 0

        while queue:
            node, cnt = queue.popleft()  #       ，cnt       
            if node == target:  #    
                return cnt

            for i in range(4):
                for j in [1, -1]:
                    next_node = node[:i] + str((int(node[i]) + j) % 10) + node[i + 1:]

                    if next_node not in deadends:  #            
                        deadends.add(next_node)  #     
                        queue.append([next_node, cnt + 1])

        return -1

双方向検索形式
この問題は,単一ソースポイント(「0000」)単一ターゲット(入力target)の広さ優先探索である.ターゲットノードに到達すると,解ツリー内の同じ層にある他のノードも遍歴することを想像できる.その層では1つのノードを巡回するだけでよいが,実際には多くの不要なノードを巡回するため,一方向探索には最適化空間がある.単一の検索を双方向検索に変更することができます.すなわち、ソースポイントからターゲットに向かって検索するだけでなく、ターゲットからソースポイントに向かって検索することもできます.2つの方向探索が最終的に中間の位置で出会うことができる場合、ソースポイントからターゲットへの経路が存在することを示す.

from collections import deque


class Solution(object):
    def openLock(self, deadends, target):
        '''
        :type deadends: List[str]
        :type target: str
        :rtype: int
        '''
        self.deadends = set(deadends)
        if '0000' in deadends or target in deadends:  #              -1
            return -1
        if target == '0000':
            return 0

        queue_order = deque()
        queue_inorder = deque()
        queue_order.append('0000')
        queue_inorder.append(target)
        step_order=0
        step_inorder=0
        if self.queuesArrived(queue_order, queue_inorder):
            return step_order + step_inorder+1
        while queue_order and queue_inorder:  #       
            queue_order = self.queueStepAdd(queue_order)  #      
            step_order=step_order+1
            if self.queuesArrived(queue_order, queue_inorder):
                return step_order + step_inorder + 1
            queue_inorder = self.queueStepAdd(queue_inorder)    #      
            step_inorder = step_inorder + 1
            if self.queuesArrived(queue_order, queue_inorder):
                return step_order + step_inorder + 1
        return -1

    def queueStepAdd(self, queue):
        if len(queue)==0:
            return None
        length=len(queue)
        for index in range(length):
            node = queue.popleft()  #       
            for i in range(4):
                for j in [1, -1]:
                    next_node = node[:i] + str((int(node[i]) + j) % 10) + node[i + 1:]
                    if next_node not in self.deadends:  #            
                        self.deadends.add(next_node)  #     
                        queue.append(next_node)
        return queue
    def queuesArrived(self,queue1,queue2): #        
        length = len(queue1)
        for index in range(length):
            node = queue1[index]  #       
            for i in range(4):
                for j in [1, -1]:
                    next_node = node[:i] + str((int(node[i]) + j) % 10) + node[i + 1:]
                    if next_node in set(queue2):
                        return True
        return False