Giả sử chúng ta có N phòng và chúng ta bắt đầu ở phòng 0. Trong mỗi phòng tồn tại một số phân biệt 0, 1, 2, ..., N-1 và mỗi phòng có thể có một số chìa khóa để vào phòng tiếp theo. Nói cách khác, mỗi phòng tôi có một danh sách các phòng khóa [i], và mỗi phòng khóa [i] [j] là một số nguyên trong [0, 1, ..., N-1] trong đó N =số phòng. Một phòng chính [i] [j] =v, điều này mở ra phòng với số v Vì vậy, nếu đầu vào là [[1], [2], [3], []]. thì đầu ra sẽ là true. Có một vài điểm nữa mà chúng ta cần lưu ý -
- Ban đầu, tất cả các phòng đều bắt đầu bị khóa (ngoại trừ phòng 0).
- Chúng ta có thể thoải mái đi lại giữa các phòng.
- Chúng ta nên trả về true nếu và chỉ khi chúng ta có thể vào mọi phòng.
Vì vậy, chúng ta sẽ bắt đầu từ phòng 0 và lấy chìa khóa 1, sau đó đến phòng 1, lấy chìa khóa cho 2, phòng dạng 2, lấy chìa khóa cho 3, sau khi ghé thăm 3, nếu tất cả các phòng đều đã truy cập, sau đó trả về true.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- tạo một hàng đợi trống và tạo một mảng đã truy cập cho tất cả các phòng và đặt là false
- queue:=addRooms (phòng, 0, hàng đợi, đã ghé thăm)
- đã ghé thăm [0]:=Ture
- trong khi hàng đợi có một số phần tử
- queue:=addRooms (phòng, hàng đợi [0], hàng đợi, đã ghé thăm)
- đánh dấu đã ghé thăm [hàng đợi [0]] là đúng,
- xóa phần tử khỏi hàng đợi
- trả về true, khi tất cả các phần tử đều đúng trong mảng đã truy cập
- AddRoom () sẽ lấy phòng, lập chỉ mục, hàng đợi và mảng đã truy cập, điều này sẽ giống như
- cho tôi trong mảng [chỉ mục] phòng
- nếu tôi không được đến thăm, hãy chèn tôi vào hàng đợi
- hàng đợi trả lại
Ví dụ (Python)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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],[]]
Đầu ra
true