钥匙开门取宝藏

自己定义input, 房间，房间里可能有宝藏，钥匙（可以链接两个不相通的房间），问从一个房间开始能不能找到宝藏。

大概思路其实就是用stack来dfs，然后找到钥匙就存在keys里面，如果stack空了就用钥匙解锁新的房间。解锁房间的时候要确认这个钥匙种的其中一个房间被访问过，才能开另外一个房间。

class Room(object):
    def __init__(self):
        self.key = None
        self.treasure = False
        self.neighbors = []

class Solution(object):
    def canFind(self, room):
        stack = [room]
        keys = []
        visited = set()
        while stack or keys:
            # if no room to visit
            # use key to open new rooms
            if not stack:
                while keys:
                    a, b = keys.pop()
                    if b in visited:
                        stack.append(a)
                    if a in visited:
                        stack.append(b)


            cur = stack.pop()
            visited.add(cur)

            if cur.treasure:
                return True

            for neighbor in cur.neighbors:
                if neighbor.key:
                    keys.append(neighbor.key)
                stack.append(neighbor)
        return False

# a -> b(key=a<->c) and  c(Treasure=True)
a = Room()
b = Room()
c = Room()
c.treasure = True
a.neighbors = [b]
b.key = (a, c)
s = Solution()
print s.canFind(a)