841.钥匙和房间

链接：841.钥匙和房间
难度：Medium
标签：深度优先搜索、广度优先搜索、图
简介：有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，...，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j] 由 [0,1，...，N-1] 中的一个整数表示，其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。最初，除 0 号房间外的其余所有房间都被锁住。你可以自由地在房间之间来回走动。如果能进入每个房间返回 true，否则返回 false。

题解 1 - typescript

• 编辑时间：2020-08-31
• 执行用时：88ms
• 内存消耗：39.4MB
• 编程语言：typescript
• 解法介绍：深度优先搜索。

function canVisitAllRooms(rooms: number[][]): boolean {
  const N = rooms.length;
  const visitedRooms = new Set<number>();
  visit(0);
  return N === visitedRooms.size;
  function visit(room: number) {
    if (visitedRooms.has(room)) return;
    visitedRooms.add(room);
    for (const nextRoom of rooms[room]) {
      visit(nextRoom);
    }
  }
}