#pragma once

#include "dungeon.h"

#include <stdexcept>
#include <unordered_set>
#include <queue>

Room* FindFinalRoom(Room* starting_room) {
    std::unordered_set<std::string> keys;
    std::unordered_set<Door*> doors;
    std::unordered_set<Room*> used_rooms;
    std::queue<Room*> queue;
    queue.push(starting_room);
    used_rooms.insert(starting_room);
    Room* result = nullptr;
    while (!queue.empty() && result == nullptr) {
        Room* cur_room = queue.front();
        queue.pop();
        if (cur_room->IsFinal()) {
            result = cur_room;
            break;
        }
        for (size_t i = 0; i < cur_room->NumKeys(); ++i) {
            std::string key = cur_room->GetKey(i);
            keys.insert(key);
            for (auto& door : doors) {
                door->TryOpen(key);
                if (door->IsOpen()) {
                    if (used_rooms.find(door->GoThrough()) == used_rooms.end()) {
                        queue.push(door->GoThrough());
                        used_rooms.insert(door->GoThrough());
                    }
                    doors.erase(door);
                }
            }
        }
        for (size_t i = 0; i < cur_room->NumDoors(); ++i) {
            Door* cur_door = cur_room->GetDoor(i);
            for (auto& key : keys) {
                cur_door->TryOpen(key);
            }
            if (cur_door->IsOpen()) {
                if (used_rooms.find(cur_door->GoThrough()) == used_rooms.end()) {
                    queue.push(cur_door->GoThrough());
                    used_rooms.insert(cur_door->GoThrough());
                }
            } else {
                doors.insert(cur_door);
            }
        }

    }
    return result;
}