Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Appearance settings

Latest commit

 

History

History
History
53 lines (51 loc) · 1.84 KB

File metadata and controls

53 lines (51 loc) · 1.84 KB
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//
// Solution1298.cpp
// Algorithm
//
// Created by Pancf on 2020/8/9.
// Copyright © 2020 Pancf. All rights reserved.
//
#include "Solution1298.hpp"
#include <set>
#include <queue>
// 遍历initialBoxes,可打开的盒子加到一个queue中,可见但不可打开的加到一个vector中
// loop:
// queue.pop,把candies[i]加到总数中,遍历keys[i],已在vector中且状态为不可打开的加到queue中,然后将盒子状态置为打开。
// 遍历containedBoxes[i],将状态为打开的盒子加到queue中,否则就加到vector中。
// goto loop until queue.isEmpty
int Solution1298::maxCandies(vector<int>& status,
vector<int>& candies,
vector<vector<int>>& keys,
vector<vector<int>>& containedBoxes,
vector<int>& initialBoxes)
{
int sumOfCandies = 0;
std::queue<int> openedBoxes; // 已打开的盒子
vector<bool> reachableButClosedBoxes(status.size(), false); // 能接触到但未打开的盒子
for (auto &box : initialBoxes) {
if (status[box]) {
openedBoxes.push(box);
} else {
reachableButClosedBoxes[box] = true;
}
}
while (!openedBoxes.empty()) {
sumOfCandies += candies[openedBoxes.front()];
for (auto &box : keys[openedBoxes.front()]) {
if (reachableButClosedBoxes[box]) {
openedBoxes.push(box);
reachableButClosedBoxes[box] = false;
}
status[box] = 1;
}
for (auto &box : containedBoxes[openedBoxes.front()]) {
if (status[box]) {
openedBoxes.push(box);
} else {
reachableButClosedBoxes[box] = true;
}
}
openedBoxes.pop();
}
return sumOfCandies;
}
Morty Proxy This is a proxified and sanitized view of the page, visit original site.