参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

841.钥匙和房间

有 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：

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

示例 2：

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

思路

本题其实给我们是一个有向图，意识到这是有向图很重要！

图中给我的两个示例： [[1],[2],[3],[]] [[1,3],[3,0,1],[2],[0]]，画成对应的图如下：

我们可以看出图1的所有节点都是链接的，而图二中，节点2 是孤立的。

这就很容易让我们想起岛屿问题，只要发现独立的岛，就是不能进入所有房间。

此时也容易想到用并查集的方式去解决。

但本题是有向图，在有向图中，即使所有节点都是链接的，但依然不可能从0出发遍历所有边。给大家举一个例子：

图3：[[5], [], [1, 3], [5]] ，如图：

在图3中，大家可以发现，节点0只能到节点5，然后就哪也去不了了。

所以本题是一个有向图搜索全路径的问题。只能用深搜（DFS）或者广搜（BFS）来搜。

关于DFS的理论，如果大家有困惑，可以先看我这篇题解： DFS理论基础

以下dfs分析大家一定要仔细看，本题有两种dfs的解法，很多题解没有讲清楚。看完之后相信你对dfs会有更深的理解。

深搜三部曲：

确认递归函数，参数

需要传入二维数组rooms来遍历地图，需要知道当前我们拿到的key，以至于去下一个房间。

同时还需要一个数组，用来记录我们都走过了哪些房间，这样好知道最后有没有把所有房间都遍历的，可以定义一个一维数组。

所以递归函数参数如下：

// key 当前得到的可以 
// visited 记录访问过的房间 
void dfs(const vector<vector<int>>& rooms, int key, vector<bool>& visited) {

确认终止条件

遍历的时候，什么时候终止呢？

这里有一个很重要的逻辑，就是在递归中，我们是处理当前访问的节点，还是处理下一个要访问的节点。

这决定终止条件怎么写。

首先明确，本题中什么叫做处理，就是 visited数组来记录访问过的节点，该节点默认数组里元素都是false，把元素标记为true就是处理本节点了。

如果我们是处理当前访问的节点，当前访问的节点如果是 true ，说明是访问过的节点，那就终止本层递归，如果不是true，我们就把它赋值为true，因为这是我们处理本层递归的节点。

代码就是这样：

// 写法一：处理当前访问的节点
void dfs(const vector<vector<int>>& rooms, int key, vector<bool>& visited) {
    if (visited[key]) { // 本层递归是true，说明访问过，立刻返回
        return;
    }
    visited[key] = true; // 给当前遍历的节点赋值true 
    vector<int> keys = rooms[key];
    for (int key : keys) {
        // 深度优先搜索遍历
        dfs(rooms, key, visited);
    }
}

如果我们是处理下一层访问的节点，而不是当前层。那么就要在深搜三部曲中第三步：处理目前搜索节点出发的路径的时候对节点进行处理。

这样的话，就不需要终止条件，而是在搜索下一个节点的时候，直接判断下一个节点是否是我们要搜的节点。

代码就是这样的：

// 写法二：处理下一个要访问的节点
void dfs(const vector<vector<int>>& rooms, int key, vector<bool>& visited) {
    // 这里 没有终止条件，而是在 处理下一层节点的时候来判断
    vector<int> keys = rooms[key];
    for (int key : keys) { 
        if (visited[key] == false) { // 处理下一层节点，判断是否要进行递归
            visited[key] = true;
            dfs(rooms, key, visited);
        }       
    }
}

可以看出，如果看待我们要访问的节点，直接决定了两种不一样的写法，很多录友对这一块很模糊，可能做过这道题，但没有思考到这个维度上。

处理目前搜索节点出发的路径

其实在上面，深搜三部曲第二部，就已经讲了，因为终止条件的两种写法，直接决定了两种不一样的递归写法。

这里还有细节：

看上面两个版本的写法中，好像没有发现回溯的逻辑。

我们都知道，有递归就有回溯，回溯就在递归函数的下面，那么之前我们做的dfs题目，都需要回溯操作，例如：797.所有可能的路径， 为什么本题就没有回溯呢？

代码中可以看到dfs函数下面并没有回溯的操作。

此时就要在思考本题的要求了，本题是需要判断 0节点是否能到所有节点，那么我们就没有必要回溯去撤销操作了，只要遍历过的节点一律都标记上。

那什么时候需要回溯操作呢？

当我们需要搜索一条可行路径的时候，就需要回溯操作了，因为没有回溯，就没法“调头”，如果不理解的话，去看我写的 797.所有可能的路径的题解。

以上分析完毕，DFS整体实现C++代码如下：

// 写法一：处理当前访问的节点
class Solution {
private:
    void dfs(const vector<vector<int>>& rooms, int key, vector<bool>& visited) {
        if (visited[key]) {
            return;
        }
        visited[key] = true;
        vector<int> keys = rooms[key];
        for (int key : keys) {
            // 深度优先搜索遍历
            dfs(rooms, key, visited);
        }
    }
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        vector<bool> visited(rooms.size(), false);
        dfs(rooms, 0, visited);
        //检查是否都访问到了
        for (int i : visited) {
            if (i == false) return false;
        }
        return true;
    }
};

写法二：处理下一个要访问的节点
class Solution {
private:  
    void dfs(const vector<vector<int>>& rooms, int key, vector<bool>& visited) {
        vector<int> keys = rooms[key];
        for (int key : keys) { 
            if (visited[key] == false) {
                visited[key] = true;
                dfs(rooms, key, visited);
            }       
        }
    }
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        vector<bool> visited(rooms.size(), false); 
        visited[0] = true; // 0 节点是出发节点，一定被访问过
        dfs(rooms, 0, visited);  
        //检查是否都访问到了
        for (int i : visited) {
            if (i == false) return false;
        }
        return true;
    }
};

本题我也给出 BFS C++代码，BFS理论基础，代码如下：

class Solution {
bool bfs(const vector<vector<int>>& rooms) {
    vector<int> visited(rooms.size(), 0); // 标记房间是否被访问过
    visited[0] = 1; //  0 号房间开始
    queue<int> que;
    que.push(0); //  0 号房间开始

    // 广度优先搜索的过程
    while (!que.empty()) {
        int key = que.front(); que.pop();
         vector<int> keys = rooms[key];
         for (int key : keys) {
             if (!visited[key]) {
                 que.push(key);
                 visited[key] = 1;
             }
         }
    }
    // 检查房间是不是都遍历过了
    for (int i : visited) {
        if (i == 0) return false;
    }
    return true;

}
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        return bfs(rooms);
    }
};

其他语言版本

Java

class Solution {
     private void dfs(int key, List<List<Integer>>  rooms, List<Boolean> visited) {
        if (visited.get(key)) {
            return;
        }
        visited.set(key, true);
        for (int k : rooms.get(key)) {
            // 深度优先搜索遍历
            dfs(k, rooms, visited);
        }
    }
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        List<Boolean> visited = new ArrayList<Boolean>(){{
            for(int i = 0 ; i < rooms.size(); i++){
                add(false);
            }
        }};
        dfs(0, rooms, visited);
        //检查是否都访问到了
        for (boolean flag : visited) {
            if (!flag) {
                return false;
            }
        }
        return true;
    }
}

// 广度优先搜索
class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        boolean[] visited = new boolean[rooms.size()];    // 用一个 visited 数据记录房间是否被访问
        visited[0] = true;
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(0);           // 第 0 个房间标记为已访问
        while (!queue.isEmpty()) {
            int curKey = queue.poll();
            for (int key: rooms.get(curKey)) {
                if (visited[key]) continue;
                visited[key] = true;
                queue.add(key);
            }
        }
        for (boolean key: visited)
            if (!key) return false;
        return true;
    }
}

// 广度优先遍历(时间优化)
class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int count = 1;      // 用来记录可以被访问的房间数目，因为初始状态下 0 号房间可以被访问，所以置为 1
        boolean[] visited = new boolean[rooms.size()];      // 用一个 visited 数据记录房间是否被访问
        visited[0] = true;          // 第 0 个房间标记为已访问
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(0);
        while (!queue.isEmpty()) {
            int curKey = queue.poll();
            for (int key: rooms.get(curKey)) {
                if (visited[key]) continue;
                ++count;                // 每访问一个访问房间就让 count 加 1
                visited[key] = true;
                queue.add(key);
            }
        }
        return count == rooms.size();       // 如果 count 等于房间数目，表示能进入所有房间，反之不能
    }
}

python3

class Solution:
    def dfs(self, key: int, rooms: List[List[int]]  , visited : List[bool] ) :
        if visited[key] :
            return
        visited[key] = True
        keys = rooms[key]
        for i in range(len(keys)) :
            # 深度优先搜索遍历
            self.dfs(keys[i], rooms, visited)

    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        visited = [False for i in range(len(rooms))]

        self.dfs(0, rooms, visited)

        # 检查是否都访问到了
        for i in range(len(visited)):
            if not visited[i] :
                return False
        return True

Go

func dfs(key int, rooms [][]int, visited []bool ) {
	if visited[key] {
		return;
	}

	visited[key] = true
	keys := rooms[key]
	for _ , key := range keys {
		// 深度优先搜索遍历
		dfs(key, rooms, visited);
	}
}

func canVisitAllRooms(rooms [][]int) bool {
	visited := make([]bool, len(rooms));
	dfs(0, rooms, visited);
	//检查是否都访问到了
	for i := 0; i < len(visited); i++ {
		if !visited[i] {
			return false;
		}
	}
	return true;
}

JavaScript

//DFS
var canVisitAllRooms = function(rooms) {
    const dfs = (key, rooms, visited) => {
        if(visited[key]) return;
        visited[key] = 1;
        for(let k of rooms[key]){
            // 深度优先搜索遍历
            dfs(k, rooms, visited);
        }
    }
    const visited = new Array(rooms.length).fill(false);
    dfs(0, rooms, visited);
    //检查是否都访问到了
    for (let i of visited) {
        if (!i) {
            return false;
        }
    }
    return true;
};

//BFS
var canVisitAllRooms = function(rooms) {
    const bfs = rooms => {
        const visited = new Array(rooms.length).fill(0); // 标记房间是否被访问过
        visited[0] = 1; // 0 号房间开始
        const queue = []; //js数组作为队列使用
        queue.push(0); //  0 号房间开始
        // 广度优先搜索的过程
        while(queue.length !== 0){
            let key = queue[0];
            queue.shift();
            for(let k of rooms[key]){
                if(!visited[k]){
                    queue.push(k);
                    visited[k] = 1;
                }
            }
        }
        // 检查房间是不是都遍历过了
        for(let i of visited){
            if(i === 0) return false;
        }
        return true;
    }
    return bfs(rooms);
};

TypeScript

// BFS
// rooms :就是一个链接表 表示的有向图
// 转换问题就是，一次遍历从 0开始 能不能 把所有的节点访问了,实质问题就是一个
// 层序遍历
function canVisitAllRooms(rooms: number[][]): boolean {
  const n = rooms.length;
  //  cnt[i] 代表节点 i 的访问顺序， cnt[i] = 0, 代表没被访问过
  let cnt = new Array(n).fill(0);
  let queue = [0];
  cnt[0]++;
  while (queue.length > 0) {
    const from = queue.shift();
    for (let i = 0; i < rooms[from].length; i++) {
      const to = rooms[from][i];
      if (cnt[to] == 0) {
        queue.push(to);
        cnt[to]++;
      }
    }
  }
  // 只要其中有一个节点 没被访问过，那么就返回 false
  return cnt.every((item) => item != 0);
}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

0841.钥匙和房间.md

0841.钥匙和房间.md

841.钥匙和房间

思路

其他语言版本

Java

python3

Go

JavaScript

TypeScript

Files

0841.钥匙和房间.md

Latest commit

History

0841.钥匙和房间.md

File metadata and controls

841.钥匙和房间

思路

其他语言版本

Java

python3

Go

JavaScript

TypeScript