APCS實作解題：開啟寶盒 （112年6月）

2023 年 6 月 20 日
| 尚無留言

題目：https://zerojudge.tw/ShowProblem?problemid=k734

簡易說明：有n個盒子，m把鑰匙。開啟每個盒子需要k把鑰匙。每一盒子打開後可以釋放出其他鑰匙。一開始得到m鑰匙當中的t把鑰匙，經過連鎖反應之後，共有多少盒子可被打開？

解題概念

可看作一個message passing問題, 圖形上用k-node與b-node代表key與box之間的關係。如下圖：

  • k-node的數值只有兩種：0或1. 代表被釋出與否
  • b-node的數值在0~k之間，代表目前收集到的鑰匙數量
  • 重複的讓k-node, b-node將本身的數值傳給和他連接的nodes. 直到沒有未使用的key爲止
  • 用一個queue或stack存下所有的key. 決定以上步驟是否停止

以題目提供的測資2爲例，兩種node之間的訊息交換迭代關係如下

Python 解（通過測資AC）

import sys

n,m,k=[int(x) for x in sys.stdin.readline().split()]
keys=[int(x) for x in sys.stdin.readline().split()]
 
boxKeys=[[] for i in range(m)]
for i in range(n):
    for ki in [int(x) for x in sys.stdin.readline().split()]:
        boxKeys[ki].append(i)

 

keysInBox=[]
for i in range(n):
    keysInBox.append([int(x) for x in sys.stdin.readline().split()])
 

vldKeyCnt=[0]*n
nOpenBox=0
keyIdx=1
while keyIdx < len(keys):
    key0=keys[keyIdx]
    keyIdx+=1
    for box in boxKeys[key0]:
        vldKeyCnt[box]+= 1
        if vldKeyCnt[box] == k:
            nOpenBox+=1
            for newKey in keysInBox[box]:
                if boxKeys[newKey]:
                    keys.append(newKey)
    boxKeys[key0]=[]
 
print(nOpenBox)

C++ 解 (通過測資AC)

輸入若std::cin時間約是scanf的三倍。有些測資會TLE. 改成scanf就AC 😆

#include<stdio.h>
#include<stdlib.h>
#include <vector>
using namespace std;
 
int main(){
    // temp input
    int tt; 
    //n, m, k
    int n,m,k;
    //cin >> n >> m >> k ;
    scanf("%d%d%d", &n, &m, &k);
  

    // t
    int t;
    //cin >> t;
    scanf("%d",&t);


    // K nodes' values
    vector<int> valuesK(m, 0);
     
  
    // initial keys
    vector<int> keys;
    for(int i = 0; i < t; i++){ 
        
        //cin >> tt;
        scanf("%d",&tt);
        valuesK[tt] = 1;
        keys.push_back(tt);
    }

    // K's neighbors and B nodes'' values
    vector<vector<int> > neighborK;
    vector<int> valuesB(n,0);  
    vector< vector<int>> requiredB;
    vector< vector<int>> releasedB;

    requiredB.resize(n);
    releasedB.resize(n);
    neighborK.resize(m);
    
    for(int i = 0; i < n; i++){
        for(int j=0; j < k; j++){
            //cin >> tt;
            scanf("%d",&tt);
            requiredB[i].push_back(tt);     
            neighborK[tt].push_back(i);        
        }
    }

    for(int i = 0; i < n; i++){
        for(int j=0; j < k; j++){
            //cin >> tt;
            scanf("%d",&tt);
            releasedB[i].push_back(tt);   
              
        }
    }

    
    // begin message passing

    vector<int> isOpen(n,0);
    vector<int> mark(m,0);
    int nOpen = 0;
    while (keys.size() > 0) {

        int i = keys.back();
        keys.pop_back();

        if(mark[i]){ 
            continue;

        }
            
 

        mark[i] = 1;

        for(int j0=0; j0 < neighborK[i].size(); j0++){
 
            int j = neighborK[i][j0];
            if(isOpen[j]==1){
                continue;
            }
        
            valuesB[j] +=1;

  
            if (valuesB[j]==k){
                nOpen +=1;
                isOpen[j] = 1;
                for(int j2=0; j2 < k; j2 ++ ){
                    keys.push_back(releasedB[j][j2]);
                   
                }        
            }
        }    


    }

    //cout << nOpen << endl;
    printf("%d\n",nOpen);
    
}
APCS