841. 钥匙和房间

841. 钥匙和房间

题目描述

简单说： 就是给定一个二维数组rooms， rooms[i] 代表的是房间，房间内有n把钥匙 rooms[i][j], 获得所有房间内的钥匙后能不能把房间都打开

示例1

输入: [[1],[2],[3],[]]
输出: true
解释:  
我们从 0 号房间开始，拿到钥匙 1。
之后我们去 1 号房间，拿到钥匙 2。
然后我们去 2 号房间，拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间，我们返回 true。

示例2

输入：[[1,3],[3,0,1],[2],[0]]
输出：false
解释：我们不能进入 2 号房间。

分析

方法一

直接暴力破解， 就是遍历数组，把数组中的值放到 Set 里面，然后最后遍历一次状态数组即可

方法二

用递归

• 建立状态机。
• 建立递归函数
  • 当 当前房间的状态为 true 的时候，那么 表示这个房间已经进来过了，所以不用再继续遍历了
  • 当 当前房间的状态为 false的时候，那么表示当前房间没去过，把当前房间设置为true, 然后遍历当前房间的钥匙，继续递归
• 最后，遍历上面的状态机，如果有一个为false, 那么返回false，只有全部为true才返回false

代码

/**
 * @param {number[][]} rooms
 * @return {boolean}
 */
var canVisitAllRooms = function(rooms) {
    let length = rooms.length;
    let result = Array(length).fill(false);

    setStatus(result, rooms, 0);

    for(let i = 0; i < result.length; i++) {
        if(!result[i]) {
            return false
        }
    }
    return true
};

var setStatus = function(result, rooms, roomId) {
    if(result[roomId]) {
        return ;
    }

    const roomData = rooms[roomId];
    result[roomId] = true
    for(let i = 0; i < roomData.length; i++) {
        setStatus(result, rooms, roomData[i])
    }

}