题解 | 你能从盒子里获得的最大糖果数

题干分析：

题设所给的信息有些多，大致内容总结如下：

• 题设情景给我们n个盒子，编号0，1，2……，n-1
• 初始状态字数组status，标识每个盒子初始状态是开（1）还是闭（0）
• 糖果数数组candies，记录每个盒子种的糖果数
• 钥匙数组keys，记录每个盒子打开后内含的钥匙编号，获得的钥匙能够打开与其编号对应的盒子
• 内含盒子数组containedBoxes， 记录每个盒子打开后内含的盒子编号
• 初始给予的盒子数组initialBoxes，记录题设情景初始给予我们的盒子编号

算法思路：

总体思路是状态化访问。题设的盒子一开始只有两种状态：开/闭，而我们是否拥有这个盒子其实也算两种状态（注意这里的拥有不包含未打开盒子中内含的盒子）。我们扩展状态为四种后以初始盒子为翘板通过状态化访问能够到达的所有盒子并更新其状态（本质是一种模拟），最后再遍历这些盒子，找到状态标记为“拥有且打开”的盒子并累加其中的糖果数输出即可。

实现代码：

class Solution {
    // 定义状态码
    enum Statu {
        CLOSE_NOT_HAVE,
        OPEN_NOT_HAVE,
        CLOSE_HAVE,
        OPEN_HAVE,
        HAVE = 2,
        OPEN = 1
    };
    
    /**
     * 通过idx盒子标记能打开的盒子（本质是一种DFS）
     * 
     * @param idx 盒子idx
     */
    void open(int idx, vector<int> &status, vector<vector<int>> &keys) {
        if (keys[idx].empty()) return;
        auto tmp = keys[idx];
        keys[idx].clear();
        for (auto canOpen : tmp) {
            if (status[canOpen] % 2 == 0) status[canOpen] += OPEN;
            if (status[canOpen] == OPEN_HAVE) open(canOpen, status, keys);
        }
    }
public:
    /**
     * 获得的最大糖果数
     *
     * @param status 状态码，初始0表示关闭，1表示开启
     * @param candies 每个box的糖果数
     * @param keys 每个box内含有的钥匙
     * @param containedBoxes 每个盒子内含的盒子
     * @param initialBoxes 初始拥有的盒子
     * @return 最多获得的糖果数
     */
    int maxCandies(
        vector<int> &status, vector<int> &candies,
        vector<vector<int> > &keys, vector<vector<int> > &containedBoxes,
        vector<int> &initialBoxes
    ) {
        // BFS
        while (!initialBoxes.empty()) {
            auto tmp = initialBoxes;
            initialBoxes.clear();

            for (auto idx : tmp) {
                // 标记拥有
                if (status[idx] < CLOSE_HAVE) status[idx] += HAVE;
                // 标记能打开
                if (status[idx] == OPEN_HAVE) open(idx, status, keys);
            }
          	// 前面为状态更新，需要与非状态更新部分进行隔离，不然进行状态判定时可能不为最新状态导致出错
            for (auto idx : tmp) {
                // 获取新盒子
                if (status[idx] == OPEN_HAVE && !containedBoxes[idx].empty()) {
                    for (auto have : containedBoxes[idx]) initialBoxes.push_back(have);
                }
            }
        }

      	// 遍历获取糖果数
        int ans = 0;
        for (int i = 0; i < status.size(); ++i) {
            if (status[i] == OPEN_HAVE) ans += candies[i];
        }
        return ans;
    }
};

复杂度分析：

• 时间复杂度：针对BFS访问部分，每个盒子最多被访问一次，时间复杂度为O（n）；针对DFS开盒部分，每个钥匙对应的盒子均需要被访问，时间复杂度为O（k），k为钥匙总数；最后的遍历所有盒子时间复杂度为O（n）。总计时间复杂度为O（n + k）。
• 空间复杂度：BFS访问暂存数组使用原有的initialBoxes数组进行复用，可视为不占用额外空间；状态数组复用原status数组，不占用额外空间；DFS递归开盒最高递归深度占用空间O（n）占主体。总计空间复杂度为O（n）。