题目来源:LeetCode 841。保留原题图语义,将函数参数与返回值改为标准输入输出。
学习目标
前置知识
先阅读 6.3 图的遍历与连通性。环境需要 Node.js、pnpm 和支持 C++17 的编译器;Make 可选,可用下方 pnpm 命令替代。
题目
有 n 个房间,最初只有房间 0 打开。进入房间后可以取得其中所有钥匙,每把编号为 v 的钥匙可打开房间 v。每间房里的钥匙可任意使用,不会消耗。判断能否进入全部房间。
输入格式
第一行 n。随后 n 行对应房间 0..n-1,每行先给钥匙数 k,再给 k 个钥匙编号。空钥匙列表写作 0。
数据范围
2 <= n <= 1000,每间房 0 <= k <= min(n,1000),总钥匙数 1..3000。钥匙编号 0..n-1;同一房间内编号互异,不同房间可有相同钥匙,允许指向本房间的钥匙。
输入为单组有效数据,所有整数和命令按空白分隔。自动评分不包含非法编号、非法命令或违反上述限制的图,不需要额外输出输入校验提示。
输出格式
可以访问全部房间输出 1,否则输出 0。
只向标准输出写入答案;调试信息写入标准错误。按题面规定分行,评分按空白分隔的 token 比较。
样例
样例输入
4
1 1
1 2
1 3
0样例输出
1依次进入 0、1、2、3,沿途拿到下一间房的钥匙,因此所有房间都能访问。
实现任务
修改本题目录中的 student/main.cpp,完成 TODO 标记的算法。输入输出骨架可以保留,完整参考实现单独位于 solution/main.cpp。
- 将每个房间的钥匙作为该顶点的有向出边。
- 仅从房间 0 遍历,统计不同的已访问房间数量。
正常、边界与错误情况
- 正常情况:按题目定义处理全部输入,输出与输入边的排列顺序无关。
- 房间 0 没有钥匙:n>=2,因此输出 0。
- 未开放房间之间形成钥匙环:它们仍可能无法进入。
- 本房间钥匙:不应死循环或增加访问数量。
- 常见错误:不能从每个未访问房间启动新遍历;那会把原本锁住且无钥匙可达的房间也算入。
- 非法输入不在评分范围;不要在标准输出中添加提示词、调试标记或额外解释。
运行与评分
在本 Lab 目录执行:
make doctor
make run
make run CASE=001-sample
make score未安装 Make 时,在仓库根目录执行:
pnpm lab:doctor -- labs/chapter-06/exercise/E-06-13-keys-and-rooms
pnpm lab:run -- labs/chapter-06/exercise/E-06-13-keys-and-rooms
pnpm lab:run -- labs/chapter-06/exercise/E-06-13-keys-and-rooms --case 001-sample
pnpm lab:score -- labs/chapter-06/exercise/E-06-13-keys-and-rooms本题有 20 组测试,每组 5 分,总分 100。起始代码可以编译,但尚未实现完整算法;满分需补齐 TODO。作者检查参考解、骨架与预期输出可使用 pnpm lab:verify -- labs/chapter-06/exercise/E-06-13-keys-and-rooms。
正确性说明
只有进入房间后才能取得它的钥匙,所以可进入的房间恰好是从 0 沿钥匙有向边可达的顶点。visited 保证重复钥匙和自钥匙不会重复计数。
复杂度分析
设总钥匙数为 K,时间和空间均为 O(n+K)。
完成清单
思考与复盘
- 为什么把钥匙关系当成无向边会导致错误?
- “每间房的钥匙编号都在某处出现”是否足以保证全部房间可进入?