LeetCode C++ 841. Keys and Rooms【BFS/DFS】中等
发布日期:2021-07-01 02:50:50
浏览次数:2
分类:技术文章
本文共 1591 字,大约阅读时间需要 5 分钟。
There are N
rooms and you start in room 0
. Each room has a distinct number in 0, 1, 2, ..., N-1
, and each room may have some keys to access the next room.
Formally, each room i has a list of keys rooms[i]
, and each key rooms[i][j]
is an integer in [0, 1, ..., N-1]
where N = rooms.length
. A key rooms[i][j] = v
opens the room with number v
.
Initially, all the rooms start locked (except for room 0
). You can walk back and forth between rooms freely. Return true
if and only if you can enter every room.
Example 1:
Input: [[1],[2],[3],[]]Output: trueExplanation: We start in room 0, and pick up key 1.We then go to room 1, and pick up key 2.We then go to room 2, and pick up key 3.We then go to room 3. Since we were able to go to every room, we return true.
Example 2:
Input: [[1,3],[3,0,1],[2],[0]]Output: falseExplanation: We can't enter the room with number 2.
Note:
1 <= rooms.length <= 1000
0 <= rooms[i].length <= 1000
- The number of keys in all rooms combined is at most
3000
.
题意:N
个房间,开始位于 0
号房间,每个房间有一些钥匙可以进入其他房间。判断是否能够进入每个房间。
思路:DFS一遍过。这个中等题太简单了。代码如下:
class Solution { public: vectorvisited; void dfs(const vector > &rooms, int idx) { visited[idx] = true; for (const int key : rooms[idx]) if (!visited[key]) dfs(rooms, key); } bool canVisitAllRooms(vector >& rooms) { if (rooms.size() <= 1) return true; visited.resize(rooms.size()); dfs(rooms, 0); for (const bool f : visited) if (!f) return false; return true; }};
转载地址:https://memcpy0.blog.csdn.net/article/details/108332970 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
做的很好,不错不错
[***.243.131.199]2024年04月10日 09时59分22秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
linux和windows下mysql密码怎样清空!
2019-05-02
mysql logs-slave-updates (A -> B -> C)
2019-05-02
关于Java中split方法对空字符串处理问题
2019-05-02
mysql JDBC URL参数解析
2019-05-02
数据库复习(4)
2019-05-02
C# TextBox输入密码显示星号(*)
2019-05-02
1小时点击量破千万!阿里巴巴首发:MySQL高级调优笔记!全是技术重点
2019-05-02
这个GItHub上的Java项目开源了 2021最全的Java架构面试复习指南
2019-05-02
Proftpd MySQL [Step by Step]
2019-05-02
EFI Shell 命令参考
2019-05-02
HP-UX oracle RAC 双机实践
2019-05-02
解决SHELL脚本中的export无法生效的问题【转】
2019-05-02
linux中的sh脚本语法【转】
2019-05-02
Linux 内核通用链表学习小结【转】
2019-05-02
区别数据结构中的堆栈与内存中的堆栈的个人总结【转】
2019-05-02
六、判断两个单向链表是否相交
2019-05-02
七、两个有序链表合并(递归方式)
2019-05-02
C++拷贝构造函数(深拷贝,浅拷贝)【转】
2019-05-02