开锁

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param vec string字符串一维数组
# @param tar string字符串
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/e7cbabbf7e0a41ec98055ee5f3d33bbe?tpId=196&tqId=40453&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    参考：
        大神：fred-coder
    算法：
        BFS
        初始："0000"入队queue
        我们对queue中的每一个密码，按位进行扩展，选取所有可行的密码，作为下一次的扩展队列，直到找到解或者queue为空。每对当前queue的所有密码进行一次扩展，旋转次数+1。
    复杂度：
        时间复杂度：待分析
        空间复杂度：待分析
    """

    def open(self, vec, tar):
        # write code here
        def up(num):  # 向上旋转：0 -> 1 -> ... -> 9 -> 0
            if num == 9:
                num = 0
            else:
                num += 1
            return str(num)

        def down(num):  # 向下旋转：9 -> 8 -> ... -> 0 -> 9
            if num == 0:
                num = 9
            else:
                num -= 1
            return str(num)

        queue, hashSet, visited = ["0000"], set(vec), set("0000")

        res = 0
        while queue:
            sonQueue = []
            for strNum in queue:
                if strNum == tar:
                    return res
                for i in range(4):  # 密码为4位，按位枚举
                    upNum = strNum[:i] + up(int(strNum[i])) + strNum[i + 1:]
                    if upNum not in hashSet and upNum not in visited:  # 判断向上旋转得到的密码是否有效（未出现过且不在vec中）
                        sonQueue.append(upNum)
                        visited.add(upNum)
                    downNum = strNum[:i] + down(int(strNum[i])) + strNum[i + 1:]
                    if downNum not in hashSet and downNum not in visited:  # 判断向下旋转得到的密码是否有效（未出现过且不在vec中）
                        sonQueue.append(downNum)
                        visited.add(downNum)
            res += 1  # 每经过一轮对queue所有元素的枚举，旋转次数+1
            queue = sonQueue
        return -1


if __name__ == "__main__":
    sol = Solution()

    # vec, tar = ["9999", "9998", "1000"], "1001"

    vec, tar = ["8887", "8889", "8878", "8898", "8788", "8988", "7888", "9888"], "8888"

    res = sol.open(vec, tar)

    print res