# APCS實作題2023年6月第4題：開啟寶盒

> 日期：2024年8月24日
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=k734)

## 題目

### 問題描述

已知有 $n$ 個寶盒編號 $0$ 到 $n-1$ 以及 $m$ 種鑰匙編號 $0$ 到 $m-1$。一開始你有 $t$ 種鑰匙分別為 $x_1, x_2, \dots, x_t$。

每一個寶盒要打開都需要同時擁有 $k$ 種鑰匙，第 $i$ 個寶盒分別需要 $r_{i1}, r_{i2}, \dots, r_{ik}$ 種類的鑰匙。每個寶盒打開後都會得到 $k$ 種鑰匙，第 $i$ 個寶盒打開後分別會得到 $s_{1i}, s_{2i}, \dots, s_{ki}$ 種類的鑰匙，當拿到新的鑰匙之後可以繼續開啟新的寶盒。保證寶盒內的鑰匙不會重複，並且每種鑰匙可以開啟的寶盒數量不超過 $60$。

請輸出最多可以開啟多少個寶盒。
<br />

### 輸入說明

第一行輸入三個正整數 $n, m, k ~(1 \leq n, m \leq 10^5,~ 1 \leq k \leq 5)$ 代表有 $n$ 個寶盒，$m$ 種鑰匙以及每個寶盒需要的鑰匙數量 $k$。

接下來輸入一行，第一個數字 $t$ 代表一開始有的鑰匙種類數量，後面有 $t$ 個數字代表這些鑰匙分別的種類。

接下來有 $n$ 行，每一行有 $k$ 個數字，代表要開啟第 $i$ 個寶盒的第 $j$ 種鑰匙為 $r_{ij}$。

最後有 $n$ 行，每一行有 $k$ 個數字，代表開啟第 $i$ 個寶盒後得到的第 $j$ 種鑰匙為 $s_{ij}$。

配分
- 子問題一 20%：$k = 1,~ 1 \leq n, m \leq 100$
- 子問題二 20%：$k = 1,~ 1 \leq n, m \leq 10^5$
- 子問題三 60%：$1 \leq k \leq 5,~ 1 \leq n, m \leq 10^5$
<br />

### 輸出說明

輸出一個正整數，代表可以開啟的寶盒數量。
<br />

### 範例輸入1

5 5 1
2 0 1
0
2
4
3
1
1
2
4
3
3

### 範例輸出1

3

<br />

### 範例輸入2

10 8 2
3 6 5 2
5 6
2 7
2 0
4 5
5 1
3 0
4 2
2 4
5 3
5 6
5 0
0 6
1 7
3 2
2 1
7 3
4 7
4 5
4 1
7 5

### 範例輸出2

5

<br />

## Python 程式碼

### 寫法1，用自訂函式及遞迴找出所有可以開啟的寶盒及拿到的鑰匙

以範例輸入1為例，流程為

0. 原有 0、1 號鑰匙
1. 用 0 號鑰匙開啟 0 號寶盒，拿到 1 號鑰匙，目前有 0、1 號鑰匙
2. 用 1 號鑰匙開啟 4 號寶盒，拿到 3 號鑰匙，目前有 0、1、3 號鑰匙
3. 用 3 號鑰匙開啟 3 號寶盒，拿到 3 號鑰匙，目前有 0、1、3 號鑰匙
4. 沒有更多的鑰匙了，總共開啟 3 個寶盒

在第6筆測資開始，會因為遞迴深度過深而被中止；第7筆測資超時。需要再修改成不使用遞迴的版本才行。

n, m, k = map(int, input().split())  # 讀取寶盒數量 n、鑰匙種類 m、需要的鑰匙數量 k
tmp = list(map(int, input().split()))  # 讀取起始狀態
t = tmp[0]; now = tmp[1:]  # 一開始有 t 把鑰匙，鑰匙編號存入 now
needs = [k]*n  # 每個寶盒需要的鑰匙數量，預設為 k

keys = [[] for _ in range(m)]  # 每種鑰匙可以開啟的寶盒編號
for i in range(n):  # 讀取 n 行
    data = list(map(int, input().split()))  # 編號 i 的寶盒需要的鑰匙編號
    for d in data:  # 依序讀取鑰匙編號 d
        keys[d].append(i)  # 於 keys[d] 新增對的寶盒編號

avails = [[] for _ in range(n)]  # 開啟寶盒可以拿到的鑰匙編號
for i in range(n): avails[i] = list(map(int, input().split()))

""" 自訂函式，輸入鑰匙編號，找出可以開啟的寶盒，更新已有的鑰匙編號 """
def getkeys(idx):
    cur = keys[idx]  # 編號 idx 鑰匙可以開啟的寶盒編號
    for c in cur:  # 依序讀取可以開啟的寶盒編號 c
        needs[c] -= 1  # 將 c 需要的鑰匙數量減 1
        if needs[c] == 0:  # 如果已歸零，開啟寶盒，得到新的鑰匙
            for avail in avails[c]:  # 依取讀取新的鑰匙編號
                if avail not in now:  # 如果 avail 還不在 now 之中
                    now.append(avail)  # 更新已有的鑰匙編號
                    getkeys(avail)  # 遞迴，檢查是否能開啟新的寶盒
""" 結束自訂函式 """

for i in range(t):  # 執行 t 次，更新開啟每個寶盒還需要的鑰匙數量
    getkeys(now[i])

ans = 0  # 答案預設為 0
for i in range(n):  # 依序檢查每個寶盒需要的鑰匙數量，如果已經歸零則 ans 加 1
    ans += 1 if needs[i] <= 0 else 0
print(ans)  # 印出答案

<br /><br />

### 寫法2，不使用遞迴

第6筆測資超時。

n, m, k = map(int, input().split())  # 讀取寶盒數量 n、鑰匙種類 m、需要的鑰匙數量 k
st = list(map(int, input().split()))[1:]  # 待走訪的鑰匙編號
needs = [k]*n  # 每個寶盒需要的鑰匙編號，預設為 k

keys = [[] for _ in range(m)]  # 每種鑰匙可以開啟的寶盒編號
for i in range(n):  # 讀取 n 行
    data = list(map(int, input().split()))  # 編號 i 的寶盒需要的鑰匙編號
    for d in data:  # 依序讀取鑰匙編號 d
        keys[d].append(i)  # 於 keys[d] 新增對的寶盒編號

avails = [[] for _ in range(n)]  # 開啟寶盒可以拿到的鑰匙編號
for i in range(n): avails[i] = list(map(int, input().split()))

""" 主要的解題過程 """
head = 0  # 從 st 讀取資料的索引值
while head < len(st):  # 當 head 還沒有出界時繼續執行
    s = st[head]; head += 1  # 取出 st[head]，head 加 1
    cur = keys[s]  # 找到編號 s 的鑰匙可以開啟的寶盒編號
    for c in cur:  # 依序讀取可以開啟的寶盒編號 c
        needs[c] -= 1  # 將 c 需要的鑰匙數量減 1
        if needs[c] == 0:  # 如果已歸零，開啟寶盒，得到新的鑰匙
            for avail in avails[c]:  # 依取讀取新的鑰匙編號
                if avail not in st:  # 如果 avail 還沒有走訪而且不在 st 之中
                    st.append(avail)  # 將 avail 加入 st
""" 結束 while 迴圈 """

ans = 0  # 答案預設為 0
for i in range(n):  # 依序檢查每個寶盒需要的鑰匙數量，如果已經歸零則 ans 加 1
    ans += 1 if needs[i] <= 0 else 0
print(ans)  # 印出答案

<br /><br />

## C++ 程式碼

### 寫法1，用自訂函式及遞迴找出所有可以開啟的寶盒及拿到的鑰匙

程式碼運作邏輯與 Python 版本寫法1相同，費時最久約為 0.2 s，使用記憶體最多約為 22.1 MB，通過測試。為了使自訂函式不需要引入較多的參數，在程式碼第5 ~ 9行定義了一些全域變數，但是在這裡只能先定義變數名稱及種類，在 main 之中才能設定變數值。

#include <iostream>
#include <vector>
using namespace std;

int n, m, k, t;
vector<bool> now (100001);  // 目前有的鑰匙編號，要在 main 裡面設定值
vector<int> needs (100001);  // 每個寶盒需要的鑰匙數量，要在 main 裡面設定值
vector<vector<int>> keys (100001, vector<int> ());  // 每種鑰匙可以開啟的寶盒編號
vector<vector<int>> avails (100001, vector<int> ());  // 開啟寶盒可以拿到的鑰匙編號

/* 自訂函式，輸入鑰匙編號，找出可以開啟的寶盒，更新已有的鑰匙編號 */
void getkeys(int idx) {
    vector<int> cur = keys[idx];  // 編號 idx 鑰匙可以開啟的寶盒編號
    for(auto c : cur) {  // 依序讀取可以開啟的寶盒編號 c
        needs[c]--;  // 將 c 需要的鑰匙數量減 1
        if (needs[c] == 0) {  // 如果已歸零，開啟寶盒，得到新的鑰匙
            for(auto avail : avails[c]) {  // 依取讀取新的鑰匙編號
                if (!now[avail]) {  // 如果 avail 還不在 now 之中
                    now[avail] = true;  // 更新已有的鑰匙編號
                    getkeys(avail);  // 遞迴，檢查是否能開啟新的寶盒
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);  // 加速
    cin >> n >> m >> k;  // 讀取寶盒數量 n、鑰匙種類 m、需要的鑰匙數量 k
    for(int i=0; i<n; i++) {  // 設定 now 及 needs 的初始值
        needs[i] = k; now[i] = false;
    }
    cin >> t;  // 讀取起始狀態
    vector<int> have (t, 0);  // 一開始有的鑰匙
    for(int i=0; i<t; i++) { // 一開始有 t 把鑰匙，鑰匙編號存入 have
        int tmp; cin >> tmp; now[tmp] = true; have[i] = tmp;
    }

    for(int i=0; i<n; i++) {  // 讀取 n 行
        for(int j=0; j<k; j++) {  // 編號 i 的寶盒需要的鑰匙編號
            int d; cin >> d;  // 依序讀取鑰匙編號 d
            keys[d].push_back(i);  // 於 keys[d] 新增對的寶盒編號
        }
    }
    
    for(int i=0; i<n; i++) {  // 讀取 n 行
        for(int j=0; j<k; j++) {  // 編號 i 的寶盒獲得的鑰匙編號
            int a; cin >> a;  // 依序讀取鑰匙編號 a
            avails[i].push_back(a);  // 於 avails[i] 新增鑰匙編號
        }
    }
    
    for(int i=0; i<t; i++) getkeys(have[i]);   // 執行 t 次，更新開啟每個寶盒還需要的鑰匙數量
    
    int ans = 0;  // 答案預設為 0
    for(int i=0; i<n; i++) ans += needs[i]<=0 ? 1 : 0;   // 依序檢查每個寶盒需要的鑰匙數量，如果已經歸零則 ans 加 1
    cout << ans << "\n";  // 印出答案
    return 0;
}

<br /><br />

### 寫法2，改用 stack 及 set，不使用遞迴

費時最久約為 0.5 s，使用記憶體最多約為 19.1 MB，通過測試。應該是因為使用了 set 儲存已有的鑰匙，執行速度較慢。

#include <iostream>
#include <vector>
#include <set>
#include <stack>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);  // 加速
    int n, m, k; cin >> n >> m >> k;  // 讀取寶盒數量 n、鑰匙種類 m、需要的鑰匙數量 k
    int t; cin >> t;  // 一開始有的鑰匙數量
    set<int> now;  // 目前已有的鑰匙編號
    stack<int> st;  // 待走訪的鑰匙編號
    vector<bool> visited (m, false);  // 走訪狀態
    for(int i=0; i<t; i++) {  // 執行 t 次
        int tmp; cin >> tmp;  // 讀取一開始有的鑰匙編號
        now.insert(tmp); st.push(tmp);  // 將編號加入 now 及 st
    }

    vector<int> needs (n, k);  // 每個寶盒需要的鑰匙數量
    vector<vector<int>> keys (m, vector<int> ());  // 每種鑰匙可以開啟的寶盒編號
    for(int i=0; i<n; i++) {  // 讀取 n 行
        for(int j=0; j<k; j++) {  // 編號 i 的寶盒需要的鑰匙編號
            int d; cin >> d;  // 依序讀取鑰匙編號 d
            keys[d].push_back(i);  // 於 keys[d] 新增對的寶盒編號
        }
    }
    
    vector<vector<int>> avails (n, vector<int> ());  // 開啟寶盒可以拿到的鑰匙編號
    for(int i=0; i<n; i++) {  // 讀取 n 行
        for(int j=0; j<k; j++) {  // 編號 i 的寶盒獲得的鑰匙編號
            int a; cin >> a;  // 依序讀取鑰匙編號 a
            avails[i].push_back(a);  // 於 avails[i] 新增鑰匙編號
        }
    }
    
    /* 主要的解題過程 */
    while(!st.empty()) {  // st 還有資料時繼續執行
        int s = st.top(); st.pop();  // 取出並移除 st 最上面的資料
        visited[s] = true;  // 已走訪
        vector<int> cur = keys[s];  // 編號 s 鑰匙可以開啟的寶盒編號
        for(auto c : cur) {  // 依序讀取可以開啟的寶盒編號 c
            needs[c]--;  // 將 c 需要的鑰匙數量減 1
            if (needs[c] == 0) {  // 如果已歸零，開啟寶盒，得到新的鑰匙
                for(auto avail : avails[c]) {  // 依取讀取新的鑰匙編號
                    if (now.count(avail) == 0) {  // 如果 avail 還不在 now 之中
                        now.insert(avail);  // 更新已有的鑰匙編號
                        st.push(avail);  // 將 avail 加入 st
                    }
                }
            }
        }
    }
    
    int ans = 0;  // 答案預設為 0
    for(int i=0; i<n; i++) ans += needs[i]<=0 ? 1 : 0;   // 依序檢查每個寶盒需要的鑰匙數量，如果已經歸零則 ans 加 1
    cout << ans << "\n";  // 印出答案
    return 0;
}

<br /><br />

### 寫法3，由寫法2修改而成，不使用 set，用另一個陣列記錄已有的鑰匙編號

費時最久約為 0.2 s，使用記憶體最多約為 14.9 MB，通過測試。

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);  // 加速
    int n, m, k; cin >> n >> m >> k;  // 讀取寶盒數量 n、鑰匙種類 m、需要的鑰匙數量 k
    int t; cin >> t;  // 一開始有的鑰匙數量
    stack<int> st;  // 待走訪的鑰匙編號
    vector<bool> visited (m, false), have (m, false);  // 走訪狀態，已有的鑰匙編號
    for(int i=0; i<t; i++) {  // 執行 t 次
        int tmp; cin >> tmp;  // 讀取一開始有的鑰匙編號
        have[tmp] = true; st.push(tmp);  // 已有 tmp 號鑰匙，將 tmp 加入 st
    }

    vector<int> needs (n, k);  // 每個寶盒需要的鑰匙數量
    vector<vector<int>> keys (m, vector<int> ());  // 每種鑰匙可以開啟的寶盒編號
    for(int i=0; i<n; i++) {  // 讀取 n 行
        for(int j=0; j<k; j++) {  // 編號 i 的寶盒需要的鑰匙編號
            int d; cin >> d;  // 依序讀取鑰匙編號 d
            keys[d].push_back(i);  // 於 keys[d] 新增對的寶盒編號
        }
    }
    
    vector<vector<int>> avails (n, vector<int> ());  // 開啟寶盒可以拿到的鑰匙編號
    for(int i=0; i<n; i++) {  // 讀取 n 行
        for(int j=0; j<k; j++) {  // 編號 i 的寶盒獲得的鑰匙編號
            int a; cin >> a;  // 依序讀取鑰匙編號 a
            avails[i].push_back(a);  // 於 avails[i] 新增鑰匙編號
        }
    }
    
    /* 主要的解題過程 */
    while(!st.empty()) {  // st 還有資料時繼續執行
        int s = st.top(); st.pop();  // 取出並移除 st 最上面的資料
        visited[s] = true;  // 已走訪
        vector<int> cur = keys[s];  // 編號 s 鑰匙可以開啟的寶盒編號
        for(auto c : cur) {  // 依序讀取可以開啟的寶盒編號 c
            needs[c]--;  // 將 c 需要的鑰匙數量減 1
            if (needs[c] == 0) {  // 如果已歸零，開啟寶盒，得到新的鑰匙
                for(auto avail : avails[c]) {  // 依取讀取新的鑰匙編號
                    if (!have[avail]) {  // 如果還沒有 avail 號鑰匙
                        have[avail] = true;  // 更新已有的鑰匙編號
                        st.push(avail);  // 將 avail 加入 st
                    }
                }
            }
        }
    }
    
    int ans = 0;  // 答案預設為 0
    for(int i=0; i<n; i++) ans += needs[i]<=0 ? 1 : 0;   // 依序檢查每個寶盒需要的鑰匙數量，如果已經歸零則 ans 加 1
    cout << ans << "\n";  // 印出答案
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`