ลูกอมสูงสุดจากกล่องใน C++

คำอธิบายโจทย์

มี n กล่อง แต่ละกล่อง: [status, candies, keys, containedBoxes] status=1 เปิด, 0 ปิด เริ่มจาก initialBoxes หาลูกอมมากที่สุดที่เก็บได้

ตัวอย่าง

status=[1,0,1,0], candies=[8,6,5,101], keys=[[],[],[1],[]], containedBoxes=[[1,2],[3],[],[]], initialBoxes=[0] → 19

กล่อง 0: 8 ลูกอม + กล่อง 1,2 → กล่อง 2 เปิด: 5 ลูกอม + key กล่อง 1 → กล่อง 1: 6 ลูกอม + กล่อง 3 (ไม่มี key) รวม 19

วิธีแก้ปัญหา

BFS + State tracking:

visited: กล่องที่เคยได้มือ
opened: กล่องที่เปิดแล้วเก็บลูกอม
hasKey: กล่องที่มี key
Queue ประมวลผลกล่องที่เปิดอยู่
เมื่อได้ key ใหม่ ถ้ามีกล่องนั้นใน visited → เปิดได้เลย
เมื่อเปิดกล่อง ได้ลูกอม + keys + containedBoxes

การทำงานของโค้ด

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maxCandies(vector<int>& st, vector<int>& cnt, 
                   vector<vector<int>>& k, vector<vector<int>>& cb, vector<int>& ib) {
        int ans = 0;
        queue<int> q;
        set<int> visited, opened, hasKey;
        
        for(int x : ib) {
            visited.insert(x);
            if(st[x] == 1) {
                ans += cnt[x];
                opened.insert(x);
                q.push(x);
            }
        }
        
        while(!q.empty()) {
            int curr = q.front(); q.pop();
            // ประมวลผล keys
            for(int x : k[curr]) {
                hasKey.insert(x);
                if(!opened.count(x) && visited.count(x)) {
                    ans += cnt[x];
                    opened.insert(x);
                    q.push(x);
                }
            }
            // ประมวลผล contained boxes
            for(int x : cb[curr]) {
                visited.insert(x);
                if(!opened.count(x) && (hasKey.count(x) || st[x]==1)) {
                    opened.insert(x);
                    ans += cnt[x];
                    q.push(x);
                }
            }
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,0,1,0}, v1 = {8,6,5,101}, v2 = {0};
    vector<vector<int>> v3 = {{},{},{1},{}}, v4 = {{1,2},{3},{0},{}};
    cout << ob.maxCandies(v, v1, v3, v4, v2);
    return 0;
}

อินพุต