Số kẹo tối đa từ các hộp trong C++

Có n hộp, mỗi hộp: [status, candies, keys, containedBoxes]. status=1 mở, 0 đóng. candies: số kẹo. keys: chỉ số hộp có thể mở. containedBoxes: hộp bên trong. Bắt đầu với initialBoxes. Có thể lấy kẹo từ hộp mở, dùng chìa khóa mở hộp khác, dùng hộp tìm được. Tìm tối đa kẹo có thể lấy.

Ví dụ: status=[1,0,1,0], candies=[8,6,5,101], keys=[[],[],[1],[]], containedBoxes=[[1,2],[3],[],[]], initialBoxes=[0] → 19. Hộp 0: 8 kẹo + hộp 1,2. Hộp 2 mở: 5 kẹo + chìa khóa hộp 1. Hộp 1: 6 kẹo + hộp 3 (không có chìa khóa). Tổng = 19.

Giải pháp

BFS mô phỏng quá trình mở hộp:

• Queue q, tập visited, opened, hasKey
• Khởi tạo: các hộp initialBoxes → visited. Nếu mở (status=1): lấy kẹo, thêm opened, push q
• While q không rỗng:
  • Lấy curr, xử lý keys[curr]: thêm hasKey, nếu đã visited và chưa opened → mở, lấy kẹo, push q
  • Xử lý containedBoxes[curr]: thêm visited, nếu có chìa khóa hoặc status=1 → mở, lấy kẹo, push q
• Trả về tổng kẹo

Ví dụ mã C++

#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 i = 0; i < ib.size(); i++) { 
            int x = ib[i]; 
            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(); 
            
            for (int i = 0; i < k[curr].size(); i++) { 
                int x = k[curr][i]; 
                hasKey.insert(x); 
                if (!opened.count(x) && visited.count(x)) { 
                    ans += cnt[x]; 
                    q.push(x); 
                    opened.insert(x); 
                } 
            } 
            
            for (int i = 0; i < cb[curr].size(); i++) { 
                int x = cb[curr][i]; 
                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; 
}

Đầu vào

{1,0,1,0}, {8,6,5,101}, {{},{},{1},{}}, {{1,2},{3},{0},{}}, {0}

Đầu ra

19