//
//  Solution1298.cpp
//  Algorithm
//
//  Created by Pancf on 2020/8/9.
//  Copyright © 2020 Pancf. All rights reserved.
//

#include "Solution1298.hpp"
#include <set>
#include <queue>

// 遍历initialBoxes，可打开的盒子加到一个queue中，可见但不可打开的加到一个vector中
// loop:
//  queue.pop，把candies[i]加到总数中，遍历keys[i]，已在vector中且状态为不可打开的加到queue中，然后将盒子状态置为打开。
//  遍历containedBoxes[i]，将状态为打开的盒子加到queue中，否则就加到vector中。
//  goto loop until queue.isEmpty
int Solution1298::maxCandies(vector<int>& status,
                             vector<int>& candies,
                             vector<vector<int>>& keys,
                             vector<vector<int>>& containedBoxes,
                             vector<int>& initialBoxes)
{
    int sumOfCandies = 0;
    std::queue<int> openedBoxes;  // 已打开的盒子
    vector<bool> reachableButClosedBoxes(status.size(), false);  // 能接触到但未打开的盒子
    for (auto &box : initialBoxes) {
        if (status[box]) {
            openedBoxes.push(box);
        } else {
            reachableButClosedBoxes[box] = true;
        }
    }
    while (!openedBoxes.empty()) {
        sumOfCandies += candies[openedBoxes.front()];
        for (auto &box : keys[openedBoxes.front()]) {
            if (reachableButClosedBoxes[box]) {
                openedBoxes.push(box);
                reachableButClosedBoxes[box] = false;
            }
            status[box] = 1;
        }
        for (auto &box : containedBoxes[openedBoxes.front()]) {
            if (status[box]) {
                openedBoxes.push(box);
            } else {
                reachableButClosedBoxes[box] = true;
            }
        }
        openedBoxes.pop();
    }
    return sumOfCandies;
}