def find_key_door_candidates(region, checked, world, player):
    dungeon = region.dungeon
    candidates = []
    checked_doors = list(checked)
    queue = deque([(region, None, None)])
    while (len(queue) > 0):
        (current, last_door, last_region) = queue.pop()
        for ext in current.exits:
            d = ext.door
            if (d and d.controller):
                d = d.controller
            if ((d is not None) and (not d.blocked) and (d.dest is not last_door) and (d.dest is not last_region) and (d not in checked_doors)):
                valid = False
                if ((0 <= d.doorListPos < 4) and (d.type in [DoorType.Interior, DoorType.Normal, DoorType.SpiralStairs])):
                    room = world.get_room(d.roomIndex, player)
                    (position, kind) = room.doorList[d.doorListPos]
                    if (d.type == DoorType.Interior):
                        valid = (kind in [DoorKind.Normal, DoorKind.SmallKey, DoorKind.Bombable, DoorKind.Dashable])
                    elif (d.type == DoorType.SpiralStairs):
                        valid = (kind in [DoorKind.StairKey, DoorKind.StairKey2, DoorKind.StairKeyLow])
                    elif (d.type == DoorType.Normal):
                        d2 = d.dest
                        if (d2 not in candidates):
                            room_b = world.get_room(d2.roomIndex, player)
                            (pos_b, kind_b) = room_b.doorList[d2.doorListPos]
                            okay_normals = [DoorKind.Normal, DoorKind.SmallKey, DoorKind.Bombable, DoorKind.Dashable, DoorKind.DungeonChanger]
                            valid = ((kind in okay_normals) and (kind_b in okay_normals))
                            if (valid and (0 <= d2.doorListPos < 4)):
                                candidates.append(d2)
                        else:
                            valid = True
                if (valid and (d not in candidates)):
                    candidates.append(d)
                if ((ext.connected_region.type != RegionType.Dungeon) or (ext.connected_region.dungeon == dungeon)):
                    queue.append((ext.connected_region, d, current))
                if (d is not None):
                    checked_doors.append(d)
    return (candidates, checked_doors)
def find_key_door_candidates(region, checked, world, player):
    dungeon = region.dungeon
    candidates = []
    checked_doors = list(checked)
    queue = deque([(region, None, None)])
    while (len(queue) > 0):
        (current, last_door, last_region) = queue.pop()
        for ext in current.exits:
            d = ext.door
            if (d and d.controller):
                d = d.controller
            if ((d is not None) and (not d.blocked) and (d.dest is not last_door) and (d.dest is not last_region) and (d not in checked_doors)):
                valid = False
                if ((0 <= d.doorListPos < 4) and (d.type in [DoorType.Interior, DoorType.Normal, DoorType.SpiralStairs])):
                    room = world.get_room(d.roomIndex, player)
                    (position, kind) = room.doorList[d.doorListPos]
                    if (d.type == DoorType.Interior):
                        valid = (kind in [DoorKind.Normal, DoorKind.SmallKey, DoorKind.Bombable, DoorKind.Dashable])
                    elif (d.type == DoorType.SpiralStairs):
                        valid = (kind in [DoorKind.StairKey, DoorKind.StairKey2, DoorKind.StairKeyLow])
                    elif (d.type == DoorType.Normal):
                        d2 = d.dest
                        if (d2 not in candidates):
                            room_b = world.get_room(d2.roomIndex, player)
                            (pos_b, kind_b) = room_b.doorList[d2.doorListPos]
                            okay_normals = [DoorKind.Normal, DoorKind.SmallKey, DoorKind.Bombable, DoorKind.Dashable, DoorKind.DungeonChanger]
                            valid = ((kind in okay_normals) and (kind_b in okay_normals))
                            if (valid and (0 <= d2.doorListPos < 4)):
                                candidates.append(d2)
                        else:
                            valid = True
                if (valid and (d not in candidates)):
                    candidates.append(d)
                if ((ext.connected_region.type != RegionType.Dungeon) or (ext.connected_region.dungeon == dungeon)):
                    queue.append((ext.connected_region, d, current))
                if (d is not None):
                    checked_doors.append(d)
    return (candidates, checked_doors)