Leetcode 841 Keys and Rooms

发表于 |

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: true
Explanation:
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: false
Explanation: We can’t enter the room with number 2.

Note:

1. 1 <= rooms.length <= 1000
2. 0 <= rooms[i].length <= 1000
3. The number of keys in all rooms combined is at most 3000.

分析：
初始在房间0，每个房间有钥匙，钥匙打开对应的门，可以在打开的门之间任意走动，问能不能打开所有的门，房间数不超过1000，每个房间内钥匙不超过1000

思路：
显然是dfs，用一个visited集合来记录走过了哪些房间，最后判断visied的长度是不是等于房间的长度即可,我觉得这道题不配是medium，应该是easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def canVisitAllRoom(rooms):
	n = len(rooms)
	visited = set()

	def dfs(u):
		if u in visited: return
		visited.add(u)
		for v in rooms[u]:
			dfs(v)

	dfs(0)
	return len(visited) == n

66 / 66 test cases passed.
difficulty: medium
Runtime: 39 ms