钥匙和房间

#2024/09/11 #图 #算法/图

1. 题目及题意

https://leetcode.cn/problems/keys-and-rooms/description/

cos-blog-832-34-20241012|648

2. 思路

看示例 1 ，这不就是一个图吗，root 是房间1 ，然后房间1 里的钥匙决定了指向哪几个房间
题设中的 rooms 就是一个邻接表表示的图

所以，我们先来看图的遍历框架

/**
 * @description 图的遍历框架
 * @param {*} rooms 代表房间的二维数组，邻接表
 * @param {*} room  代表当前房间的编号
 * @param {*} visited  代表当前房间是否已经访问过
 * @returns
 */
function dfs(rooms, room, visited) {
  if (visited[room]) {
    return;
  }
  // 前序位置，标记房间已访问
  visited[room] = true;

  for (var nextRoom of rooms[room]) {
    dfs(rooms, nextRoom, visited);
  }
}

3. 最终代码

/**
 * @description 图的遍历框架
 * @param {*} rooms 代表房间的二维数组，邻接表
 * @param {*} room  代表当前房间的编号
 * @param {*} visited  代表当前房间是否已经访问过
 * @returns
 */
function dfs(rooms, room, visited) {
  if (visited[room]) {
    return;
  }
  // 前序位置，标记房间已访问
  visited[room] = true;

  for (var nextRoom of rooms[room]) {
    dfs(rooms, nextRoom, visited);
  }
}

function canVisitAllRooms(rooms) {
  var len = rooms.length;
  // 记录每个房间是否已经访问，使用数组来表示
  var visited = new Array(len).fill(false);
  // 房间号从 0 开始
  var rootNum = 0;
  // 广度优先遍历，遍历完后，visited 中所有的值都应该为 true，否则返回 false
  dfs(rooms, 0, visited);

  for (var v of visited) {
    if (!v) {
      return false;
    }
  }
  return true;
}