# APCS 202306 第4題 開啟寶盒 (ZeroJudge k734)
[ZJ題目連結](https://zerojudge.tw/ShowProblem?problemid=k734) (此題解先說明方法再揭示範例程式，包含python與C++與C)
###### tags: `apcs`
## 方法說明
有$n$個寶盒編號與$m$種鑰匙。一開始你有某些鑰匙。每個寶盒需要$k$支鑰匙才能開啟，每開啟一個寶盒可以獲得$k$支鑰匙。這題要計算一共能開啟多少個寶盒。
基本上，這題執行以下的步驟：
```
紀錄擁有的鑰匙
重複以下步驟，直到沒有新的鑰匙：
檢查擁有的鑰匙可以開啟那些寶盒，若有，獲得該寶盒內的鑰匙
```
但是如果每次都重複檢查所有的寶盒，那麼時間會花費太多。如果我們把已經開啟的寶盒丟棄，下次不再檢查，那會稍微改善，但還是不夠好。最壞的狀況下，每次開啟一個新的寶盒，那麼要檢查的寶盒次數為$n+(n-1)+(n-2)+\ldots+1 = O(n^2)$。
**快速檢查寶盒**
* 給予每一個寶盒一個倒數計數器，紀錄該寶盒還需要多少支鑰匙才能開啟。
* 對每一支鑰匙，記錄它可以用在哪些寶盒的開啟上。
* 每當獲得一支新鑰匙時，將它可以開啟的寶盒計數錄器減一，若此時計數器歸0，則得到一個新開啟的寶盒。
如此一來，對於每支新獲得的鑰匙，我們只要花該鑰匙所開啟寶盒數的時間就可以完成檢查，因為每個鑰匙可開啟的寶盒總數等於所有寶盒需求鑰匙的總數，也是就$kn$，所以檢查盒子開啟的總時間就是$O(kn)$。因為鑰匙會有重複的，這裡我們還需要避免重複檢查相同的鑰匙，我們可以用一個表格紀錄那些鑰匙已經處理過了。
最後，每次開啟一個寶盒時，我們獲得$k$把鑰匙，對於那些新獲得的鑰匙，將其納入擁有的鑰匙，所以總共的時間複雜度是$O(kn+m)$。
這個計算過程非常類似於在一個Dag中找topological sort的流程，若不熟悉的可以參考該演算法。
## 完全解
### Python code
我們用一個串列mykey保存已經擁有但是尚未處理的鑰匙。keybox是list of list，keybox[key]是key所能開啟的寶盒編號的串列，第4\~6行讀入該資料並儲存。boxkey則是開啟寶盒後所能獲得的鑰匙，第8\~9行讀入該資料。visit是每一把鑰匙是否已經獲得的資料，deg則是每一個寶盒還缺幾把鑰匙可以開啟的計數器。
第14行開始的while迴圈會執行到mykey為空為止，每一次進入迴圈會取出一把鑰匙，因為鑰匙的先後順序無關，所以這裡我們以stack的方式來處理，每次從後方pop出來較為方便。
```python=
n,m,k = [int(x) for x in input().split()]
mykey = [int(x) for x in input().split()][1:]
keybox = [[] for i in range(m)] # list of boxes requiring key
for box in range(n): #box i
for key in [int(x) for x in input().split()]:
keybox[key].append(box)
boxkey = [] # keys in box i
for box in range(n):
boxkey.append([int(x) for x in input().split()])
visit = [False]*m # if already have key
deg = [k]*n # num of locked keys to open box
for i in mykey: visit[i]=True
mybox = 0 #opened box
while mykey: # until no more key
ikey = mykey.pop() # first or last does not matter
for b in keybox[ikey]: #unlock
deg[b] -= 1
if deg[b]!=0: continue #not opened yet
mybox += 1 # box opened
for newkey in boxkey[b]: #obtain new keys
if not visit[newkey]:
visit[newkey]=True
mykey.append(newkey)
#endwhile
print(mybox)
```
### C++ code
接下來是C++的範例程式，主要使用到vector以及vector of vector來儲存資料。我們用一個vector<int> mykey保存已經擁有但是尚未處理的鑰匙。keybox是vector of vector，keybox[key]是key所能開啟的寶盒編號，seen則是記錄每一把鑰匙是否已經獲得，用來避免重複處理相同的鑰匙。boxkey則是開啟寶盒後所能獲得的鑰匙。deg則是每一個寶盒還缺幾把鑰匙可以開啟的計數器，一開始全部都設為k。
第28行開始的while迴圈會執行到mykey為空為止，每一次進入迴圈會取出一把鑰匙，因為鑰匙的先後順序無關，所以這裡我們以stack的方式來處理，每次從後方pop出來較為方便。
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, i,j,m,t,k;
scanf("%d%d%d",&n,&m,&k);
scanf("%d",&t);
vector<int> mykey(t),deg(n,k);
vector<bool> seen(m,false);
for (i=0;i<t;i++) {
scanf("%d",&mykey[i]);
seen[mykey[i]] = true;
}
vector<vector<int>> keybox(m,vector<int>()); // key used in box
for (i=0; i<n; i++) {
for (j=0;j<k;j++) {
scanf("%d",&t);
keybox[t].push_back(i);
}
}
vector<vector<int>> boxkey(n,vector<int>()); // key in box
for (i=0; i<n; i++) {
for (j=0;j<k;j++) {
scanf("%d",&t);
boxkey[i].push_back(t);
}
}
int mybox=0; // number of open box
while (!mykey.empty()) {
int key=mykey.back();
mykey.pop_back();
for (int box: keybox[key]) {
if (--deg[box] == 0) { // opened
mybox++;
for (int p:boxkey[box]) {
if (!seen[p]) {
mykey.push_back(p);
seen[p] = true;
}
}
}
}
}
printf("%d\n",mybox);
return 0;
}
```
### C code
因為也許有些讀者對C++的vector比較不熟悉，以下則是C的版本，這裡只會使用一維與二維陣列。為了偷懶以及避免記憶體不夠，我們把主要變數都放在全域，第4~10行是我們需要的資料結構。
C使用陣列存放不定個數資料時，我們可以用一個變數表示目前陣列內的資料數。例如第7行的mykey[]，它將用來存放已經擁有但是尚未處理的鑰匙，而n_key則是目前陣列內資料的個數，將來存放時做法類似於stack。這支程式的註解已經相當清楚，搭配前面說明的方法，應該是容易了解的。
```clike=
//C version
#include <stdio.h>
#define N 100001
int seen[N]={0}; // if key is already found
int keybox[N][60]; // key i is used to open which boxes, [0] is number of box
int nkbox[N]={0}; // length of keybox[i]
int mykey[N],n_key=0; //
int deg[N]; // num of needed key for box i
int boxkey[N][5]; // the keys in box i
int mybox=0; // number of opened box
int main() {
int n, i,j,m,t,k;
scanf("%d%d%d",&n,&m,&k);
scanf("%d",&n_key);
for (i=0;i<n_key;i++) { // initial list of key
scanf("%d",&mykey[i]);
seen[mykey[i]] = 1;
}
for (i=0; i<n; i++) {
for (j=0;j<k;j++) {
scanf("%d",&t);
keybox[t][nkbox[t]++] = i; // insert
}
}
for (i=0; i<n; i++) {
for (j=0;j<k;j++) {
scanf("%d",&t);
boxkey[i][j] = t;
}
}
for (i=0;i<n;i++) deg[i]=k;
while (n_key) { // check one of my key
int ikey=mykey[--n_key]; // pop the last key
for (int i=0; i< nkbox[ikey]; i++) {
int b=keybox[ikey][i]; // a box need this key
if (--deg[b] == 0) { // if just can be opened
mybox++;
for (int j=0;j<k;j++) { // obtain key
if (seen[boxkey[b][j]]==1) continue;
seen[boxkey[b][j]] = 1;
mykey[n_key++] = boxkey[b][j]; // push into stack
}
}
}
}
printf("%d\n",mybox);
return 0;
}
```
Sign in with Wallet
Connect another wallet