当前位置:网站首页>leetcode841. 钥匙和房间(中等)
leetcode841. 钥匙和房间(中等)
2022-07-06 06:55:00 【重you小垃】
搜索的模板题
思路一:dfs
class Solution {
public:
int flag[1005] = {
0};
int dfs(vector<vector<int>>& rooms, int idx) {
int cnt = 1;
flag[idx] = 1;
for (int i = 0; i < rooms[idx].size(); ++i) {
if (!flag[rooms[idx][i]]) cnt += dfs(rooms,rooms[idx][i]);
}
return cnt;
}
bool canVisitAllRooms(vector<vector<int>>& rooms) {
return dfs(rooms, 0) == rooms.size();
}
};
思路二:bfs
class Solution {
public:
int flag[1005] = {
0};
bool canVisitAllRooms(vector<vector<int>>& rooms) {
queue<int> q;
q.push(0);
flag[0] = 1;
int cnt = 0;
while (!q.empty()) {
int frt = q.front();
q.pop();
cnt++;
for (int i = 0; i < rooms[frt].size(); ++i) {
if (!flag[rooms[frt][i]]) {
q.push(rooms[frt][i]);
flag[rooms[frt][i]] = 1;
}
}
}
return cnt == rooms.size();
}
};
边栏推荐
- Development of entity developer database application
- Day 245/300 JS foreach data cannot be updated to the object after multi-layer nesting
- How to reconstruct the class explosion caused by m*n strategies?
- 基于购买行为数据对超市顾客进行市场细分(RFM模型)
- Monotonic stack
- Depth residual network
- Explain in detail the functions and underlying implementation logic of the groups sets statement in SQL
- Introduction and underlying analysis of regular expressions
- leetcode1020. 飞地的数量(中等)
- Day 245/300 JS forEach 多层嵌套后数据无法更新到对象中
猜你喜欢
云上有AI,让地球科学研究更省力
Development of entity developer database application
Is it difficult for girls to learn software testing? The threshold for entry is low, and learning is relatively simple
19.段页结合的实际内存管理
顶测分享:想转行,这些问题一定要考虑清楚!
Basic commands of MySQL
Monotonic stack
万丈高楼平地起,每个API皆根基
My creation anniversary
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
随机推荐
Reflex WMS中阶系列3:显示已发货可换组
Erreur de type résolue avec succès: type de données « catégorie» non sous - jacente
Zhongqing reading news
前缀和数组系列
Brief introduction to the curriculum differences of colleges and universities at different levels of machine human major -ros1/ros2-
leetcode704. 二分查找(查找某个元素,简单,不同写法)
Supporting title of the book from 0 to 1: ctfer's growth road (Zhou Geng)
Office doc add in - Online CS
PCL realizes frame selection and clipping point cloud
Development of entity developer database application
My creation anniversary
【Hot100】739. 每日温度
Proteus -- Serial Communication parity flag mode
SAP SD发货流程中托盘的管理
leetcode1020. 飞地的数量(中等)
win10 64位装三菱PLC软件出现oleaut32.dll拒绝访问
How to reconstruct the class explosion caused by m*n strategies?
RichView TRVStyle 模板样式的设置与使用
云上有AI,让地球科学研究更省力
[English] Grammar remodeling: the core framework of English Learning -- English rabbit learning notes (1)