您可以从C ++盒子中获得的最大糖果

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有n个盒子，这里每个盒子都以[状态，糖果，键，containedBoxes]之类的格式给出，但有一些约束-

  • status [i]：打开box [i]时为1，关闭box [i]时为0。

  • candies [i]：是box [i]中的糖果数。

  • keys [i]：是一个数组，其中包含我们可以使用box [i]中的键打开的盒子的索引。

  • containsBoxes [i]：一个数组，其中包含在box [i]中找到的盒子的索引。

我们将从initialBoxes数组中给出的一些盒子开始。我们可以将所有糖果放入任何打开的盒子中，并且可以使用其中的键来打开新盒子，也可以使用在其中找到的盒子。

我们必须找到遵循上述规则可获得的最大糖果数量。

因此，如果输入的状态为[1,0,1,0]，糖果= [8,6,5,101]，键= [[]，[]，[1]，[]]，则containsBoxes = [ [1,2]，[3]，[]，[]]，initialBoxes = [0]，那么输出将为19。这是因为最初给我们提供了框0。我们将在其中和框中找到8个糖果。 1和2。框1没有打开，我们没有键，因此我们将打开框2。在框2中，我们将找到5个糖果和框1的键。在框1中，您将找到6个糖果和框3，但找不到框3的键，因此框3将保持关闭状态。收集的糖果总数= 8 + 5 + 6 = 19个糖果。

为了解决这个问题，我们将遵循以下步骤-

  • 回答：= 0

  • 定义一个队列q

  • 定义访问，打开，hasKey的集合

  • 对于初始化i：= 0，当i <ib的大小时，更新（将i增加1），执行-

    • ans：= ans + cnt [x]

    • 将x插入打开

    • 将x插入q

    • x：= ib [i]

    • 将x插入已访问

    • 如果st [x]与1相同，则-

    • 当（不是q为空）时，执行-

      • x：= cb [curr，i]

      • 将x插入已访问

      • 如果x未打开且x在hasKey或st [x]与1相同，则-

      • 将x插入打开

      • ans：= ans + cnt [x]

      • 将x插入q

      • x：= k [curr，i]

      • 将x插入hasKey

      • 如果x未打开且x未访问，则-

      • ans：= ans + cnt [x]

      • 将x插入q

      • 将x插入打开

      • curr：= q的第一个元素

      • 从q删除元素

      • 对于初始化i：= 0，当i <k [curr]的大小时，更新（将i增加1），执行-

      • 对于初始化i：= 0，当i <cb [curr]的大小时，更新（将i增加1），执行-

      • 返回ans

      让我们看下面的实现以更好地理解-

      示例

      #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;
            set<int> opened;
            set<int> 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;
         }
      };
      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));
      }

      输入项

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

      输出结果

      19

      以上是 您可以从C ++盒子中获得的最大糖果 的全部内容， 来源链接： utcz.com/z/326885.html

      回到顶部