Giả sử chúng ta có một danh sách các danh sách được gọi là phòng. Mỗi chỉ số i trong các phòng đại diện cho một phòng và các phòng [i] đại diện cho các chìa khóa khác nhau để mở các phòng khác. Căn phòng số 0 đang mở và chúng tôi đang ở căn phòng đó và mọi căn phòng khác đều bị khóa. Chúng tôi có thể di chuyển tự do giữa các phòng đã mở; chúng tôi phải kiểm tra xem chúng tôi có thể mở mọi phòng hay không.
Vì vậy, nếu đầu vào giống như phòng =[[2, 0], [3], [1], []], thì đầu ra sẽ là Đúng, vì chúng ta bắt đầu từ phòng 0 và có thể đi đến phòng 2 bằng khóa của nó 2. Từ phòng 2 chúng ta có thể đến phòng 1. Sau đó, lấy chìa khóa phòng 3 và mở nó. Vì vậy, tất cả đều được mở.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:
- n:=kích thước của các phòng
- ready:=một danh sách có một phần tử 0
- saw:=một tập hợp mới
- trong khi sẵn sàng không trống, hãy thực hiện
- u:=phần tử cuối cùng của sẵn sàng và xóa phần tử đó khỏi trạng thái sẵn sàng
- đánh dấu bạn là đã thấy
- đối với mỗi v trong các phòng [u], hãy thực hiện
- nếu v không được nhìn thấy, thì
- chèn v vào cuối trạng thái sẵn sàng
- nếu v không được nhìn thấy, thì
- trả về true khi kích thước của saw bằng n, ngược lại là false.
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:
Ví dụ
class Solution: def solve(self, rooms): n = len(rooms) ready = [0] seen = set() while ready: u = ready.pop() seen.add(u) for v in rooms[u]: if v not in seen: ready.append(v) return len(seen) == n ob = Solution() rooms = [ [2, 0], [3], [1], [] ] print(ob.solve(rooms))
Đầu vào
rooms = [[2, 0],[3],[1],[]]
Đầu ra
True