C++のボックスから入手できる最大のキャンディー

n個のボックスがあるとします。ここでは、各ボックスが[status、candies、keys、containedBoxes]のような形式で指定されています。いくつかの制約があります-

• status [i]：ボックス[i]が開いているときは1、ボックス[i]が閉じているときは0です。

• candies [i]：ボックス[i]内のキャンディーの数です。

• keys [i]：box[i]のキーで開くことができるボックスのインデックスを含む配列です。

• containsBoxes [i]：配列には、box[i]で見つかったボックスのインデックスが含まれています。

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つのキャンディーとボックス1のキーがあります。ボックス1には、6つのキャンディーとボックス3ですが、ボックス3のキーが見つからないため、ボックス3は閉じたままになります。集められたキャンディーの総数=8+ 5 + 6=19キャンディー。

これを解決するには、次の手順に従います-

• ans：=0

• 1つのキューを定義するq

• 訪問、オープン、hasKey

  のセットを定義します

• 初期化i：=0の場合、i

  • x：=ib [i]

  • 訪問済みにxを挿入

  • st [x]が1と同じ場合、-

    • ans：=ans + cnt [x]

    • 開いた状態にxを挿入します

    • xをqに挿入

• （qが空ではない）間、-

  • curr：=qの最初の要素

  • qから要素を削除

  • 初期化i：=0の場合、i

    • x：=k [curr、i]

    • xをhasKeyに挿入

    • xが開かれておらず、xが訪問されていない場合、-

      • ans：=ans + cnt [x]

      • xをqに挿入

      • 開いた状態にxを挿入します

  • 初期化i：=0の場合、i

    • x：=cb [curr、i]

    • 訪問済みにxを挿入

    • xが開いておらず、xがhasKeyにあるか、st [x]が1）と同じである場合、-

      • 開いた状態にxを挿入します

      • ans：=ans + cnt [x]

      • xをqに挿入

• ansを返す

理解を深めるために、次の実装を見てみましょう-

例

 #include usingnamespace std; class Solution {public：int maxCandies（vector ＆st、vector ＆cnt、vector >＆k、vector >＆cb、vector ＆ib）{int ans =0; queue  q; setが訪問しました。 setが開かれました。 set  hasKey; for（int i =0; i  v ={1,0,1,0}、v1 ={8,6,5,101}、v2 ={0}; vector > v3 ={{}、{}、{1}、{}}、v4 ={{1,2}、{3}、{0}、{}}; cout <<（ob.maxCandies（v、v1、v3、v4、v2））;} 

入力

 {1,0,1,0}、{8,6,5,101}、{{}、{}、{1}、{}}、{{1,2}、{3}、{0} 、{}}、{0} pre> 
出力
 
 19