Giả sử chúng ta có N phòng và bắt đầu từ phòng 0. Mỗi phòng chứa một số riêng biệt trong 0, 1, 2, ..., N-1, và mỗi phòng có thể có một số chìa khóa để truy cập phòng tiếp theo. Nói cách khác, mỗi phòng i có danh sách chìa khóa rooms[i], và mỗi chìa khóa rooms[i][j] là một số nguyên trong [0, 1, ..., N-1] với N = số phòng. Chìa khóa rooms[i][j] = v mở phòng có số v. Nếu đầu vào là [[1], [2], [3], []], kết quả sẽ là true.
Có thêm một số lưu ý:
- Ban đầu, tất cả các phòng đều bị khóa (trừ phòng 0).
- Chúng ta có thể đi qua lại giữa các phòng tự do.
- Chỉ trả về true nếu và chỉ nếu chúng ta có thể进入 mọi phòng.
Chúng ta sẽ bắt đầu từ phòng 0, nhặt chìa khóa 1, đi đến phòng 1, lấy chìa khóa cho phòng 2, từ phòng 2 lấy chìa khóa cho phòng 3, sau khi thăm phòng 3, nếu tất cả các phòng đều đã được thăm, trả về true.
Để giải quyết, thực hiện các bước sau:
- Tạo một hàng đợi rỗng, và mảng visited cho tất cả các phòng đặt là False
- queue := addRooms(rooms, 0, queue, visited)
- visited[0] := True
- Khi queue còn phần tử:
- queue := addRooms(rooms, queue[0], queue, visited)
- Đánh dấu visited[queue[0]] là True
- Xóa phần tử khỏi queue
- Trả về true khi tất cả phần tử trong visited đều là True
- Hàm addRoom() nhận rooms, index, queue và mảng visited:
- Với i trong rooms[index]: nếu i chưa được thăm, thêm i vào queue
- Trả về queue
Ví dụ (Python)
class Solution(object):
def canVisitAllRooms(self, rooms):
queue = []
visited = [False for i in rooms]
queue = self.add_rooms(rooms, 0, queue, visited)
visited[0] = True
while len(queue) > 0:
queue = self.add_rooms(rooms, queue[0], queue, visited)
visited[queue[0]] = True
queue.pop(0)
return all(visited)
def add_rooms(self, rooms, index, queue, visited):
for i in rooms[index]:
if not visited[i]:
queue.append(i)
return queue
ob1 = Solution()
print(ob1.canVisitAllRooms([[1], [2], [3], []]))
Đầu vào
[[1], [2], [3], []]
Kết quả
True