841. 钥匙和房间

🟠   🔖  深度优先搜索 广度优先搜索 图  🔗 力扣 LeetCode

题目

There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.

When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.

Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visitall the rooms, orfalse otherwise.

Example 1:

Input: rooms = [[1],[2],[3],[]]

Output: true

Explanation:

We visit room 0 and pick up key 1.

We then visit room 1 and pick up key 2.

We then visit room 2 and pick up key 3.

We then visit room 3.

Since we were able to visit every room, we return true.

Example 2:

Input: rooms = [[1,3],[3,0,1],[2],[0]]

Output: false

Explanation: We can not enter room number 2 since the only key that unlocks it is in that room.

Constraints:

• n == rooms.length
• 2 <= n <= 1000
• 0 <= rooms[i].length <= 1000
• 1 <= sum(rooms[i].length) <= 3000
• 0 <= rooms[i][j] < n
• All the values of rooms[i] are unique.

题目大意

有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。

当你进入一个房间，你可能会在里面找到一套 不同的钥匙 ，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。

给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true，否则返回 false。

示例 1：

输入： rooms = [[1],[2],[3],[]]

输出： true

解释：

我们从 0 号房间开始，拿到钥匙 1。

之后我们去 1 号房间，拿到钥匙 2。

然后我们去 2 号房间，拿到钥匙 3。

最后我们去了 3 号房间。

由于我们能够进入每个房间，我们返回 true。

示例 2：

输入： rooms = [[1,3],[3,0,1],[2],[0]]

输出： false

解释： 我们不能进入 2 号房间。

提示：

• n == rooms.length
• 2 <= n <= 1000
• 0 <= rooms[i].length <= 1000
• 1 <= sum(rooms[i].length) <= 3000
• 0 <= rooms[i][j] < n
• 所有 rooms[i] 的值 互不相同

解题思路

这道题目是典型的图遍历问题，可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决。

• 每个房间可以看作一个节点，每把钥匙可以看作一条边。
• 初始状态下你在第 0 个房间，并拥有一些钥匙，目标是检查是否能访问所有房间。

思路一：深度优先搜索 (DFS)

1. 初始化一个 visited 数组，用来记录是否访问过某个房间。
2. 从房间 0 开始，递归地遍历每个房间，并使用钥匙进入其他房间。
3. 如果所有房间都被访问，返回 true；否则返回 false。

复杂度分析

• 时间复杂度：O(V + E)，V 是房间数（节点数），E 是钥匙数（边数），每个房间只访问一次，每条钥匙只处理一次。
• 空间复杂度：O(V)，需要递归栈存储当前访问的房间。

---

思路二：广度优先搜索 (BFS)

1. 使用队列模拟从房间 0 开始的访问过程。
2. 遍历每个房间时，将未访问过的房间加入队列。
3. 如果遍历完所有可以访问的房间后，所有房间都标记为已访问，则返回 true；否则返回 false。

复杂度分析

• 时间复杂度：O(V + E)，V 是房间数（节点数），E 是钥匙数（边数），每个房间只访问一次，每条钥匙只处理一次。
• 空间复杂度：O(V)，需要队列存储待访问的房间。

代码

DFS 解法

/**
 * @param {number[][]} rooms
 * @return {boolean}
 */
var canVisitAllRooms = function (rooms) {
	let visited = new Array(rooms.length).fill(false); // 记录访问情况
	let count = 0; // 统计已访问的房间数

	const dfs = (room) => {
		visited[room] = true;
		count++;
		for (let key of rooms[room]) {
			if (!visited[key]) {
				dfs(key);
			}
		}
	};

	dfs(0); // 从房间 0 开始深度优先搜索
	return count === rooms.length;
};

BFS 解法

/**
 * @param {number[][]} rooms
 * @return {boolean}
 */
var canVisitAllRooms = function (rooms) {
	let visited = new Array(rooms.length).fill(false); // 记录访问情况
	let queue = [0]; // 初始化队列，从房间 0 开始
	visited[0] = true; // 标记房间 0 已访问
	let count = 1; // 统计已访问的房间数

	while (queue.length > 0) {
		let room = queue.shift();
		for (let key of rooms[room]) {
			if (!visited[key]) {
				visited[key] = true;
				queue.push(key);
				count++;
			}
		}
	}

	return count === rooms.length;
};

相关题目

题号	标题	题解	标签	难度	力扣
261	以图判树 🔒		深度优先搜索 广度优先搜索 并查集 1+	🟠	🀄️ 🔗