Python 中的钥匙和房间

pythonserver side programmingprogramming更新于 2025/11/4 6:04:17

假设我们有 N 个房间，我们从 0 号房间开始。每个房间都有一个不同的数字，范围是 0、1、2、...、N-1，每个房间可能都有一些钥匙可以进入下一个房间。换句话说，每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j] 都是 [0, 1, ..., N-1] 中的一个整数，其中 N = 房间数。钥匙 rooms[i][j] = v，这将打开编号为 v 的房间，因此如果输入是 [[1], [2], [3], []]。则输出为 true。我们还应该记住以下几点 −

最初，所有房间都是锁着的(房间 0 除外)。
我们可以自由地在房间之间走动。
当且仅当我们能进入每个房间时，我们才应该返回 true。

因此，我们将从房间 0 开始，拿起钥匙 1，然后前往房间 1，拿钥匙进入房间 2，然后进入房间 2，拿钥匙进入房间 3，在访问完房间 3 后，如果所有房间都访问过了，则返回 true。

为了解决这个问题，我们将遵循以下步骤 −

创建一个空队列，并为所有房间创建一个访问过的数组并设置为 false
queue := addRooms(rooms, 0,queue,visited)
visited[0] :=Ture
当队列中有一些元素时
- queue := addRooms(rooms,queue[0],queue,visited)
- 将visited[queue[0]]标记为true，
- 从队列中删除元素
当visited数组中的所有元素都为真时，返回true
addRoom()将获取rooms、index、queue和visited数组，如下所示
for i in rooms[index]数组
- 如果i未被访问，则将i插入队列
返回 queue

示例 (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],[]]))