Сложность: medium
Есть n комнат, пронумерованных от 0 до n - 1, и все комнаты закрыты, кроме комнаты 0. Ваша цель — посетить все комнаты. Однако вы не можете войти в закрытую комнату, не имея ключа от нее.
Когда вы посещаете комнату, вы можете найти в ней набор различных ключей. Каждый ключ имеет номер, указывающий, какую комнату он открывает, и вы можете взять их все с собой, чтобы открыть другие комнаты.
Дан массив rooms, где rooms[i] — это набор ключей, которые вы можете получить, если посетите комнату i. Верните true, если вы можете посетить все комнаты, или false в противном случае.
Пример:
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.
👨💻 Алгоритм:
1⃣Создайте массив seen для отслеживания посещенных комнат и стек stack для ключей, которые нужно использовать.
2⃣Поместите ключ от комнаты 0 в стек и отметьте комнату 0 как посещенную.
3⃣Пока стек не пуст, извлекайте ключи из стека и используйте их для открытия новых комнат, добавляя найденные ключи в стек. Если все комнаты посещены, верните true, иначе false.
😎 Решение:
class Solution {
func canVisitAllRooms(_ rooms: [[Int]]) -> Bool {
var seen = [Bool](repeating: false, count: rooms.count)
seen[0] = true
var stack = [0]
while !stack.isEmpty {
let node = stack.removeLast()
for nei in rooms[node] {
if !seen[nei] {
seen[nei] = true
stack.append(nei)
}
}
}
return !seen.contains(false)
}
}Ставь 👍 и забирай 📚 Базу знаний