【算法与数据结构】841、LeetCode钥匙和房间

本文主要是介绍【算法与数据结构】841、LeetCode钥匙和房间，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

一、题目
二、解法
三、完整代码

所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

在这里插入图片描述

二、解法

思路分析：之前的岛屿问题可以看做是无向图，因为所有连接陆地都是互通的。而本题是一个有向图，即使节点之间是连接的，也未必能进入所有的房间。以[[5], [], [1, 3], [5]]为例，从0房间开始出发，到了5房间以后哪里也去不了。因此本是一个有向图全路径搜索的问题，可以用深搜或广搜来解决。

程序如下：

class Solution {
private:void dfs(vector<vector<int>>& rooms, vector<bool>& visitRooms, int key) {	// 1、递归输入参数		// 2、递归终止条件 访问过的节点直接返回if (visitRooms[key]) return;// 3、单层递归逻辑	visitRooms[key] = true;for (int i = 0; i < rooms[key].size(); i++) {dfs(rooms, visitRooms, rooms[key][i]);}	}
public:bool canVisitAllRooms(vector<vector<int>>& rooms) {vector<bool> visitRooms = vector<bool>(rooms.size(), false);dfs(rooms, visitRooms, 0);for (int i = 0; i < visitRooms.size(); i++) {if (!visitRooms[i]) return false;}return true;}
};

复杂度分析：

时间复杂度： $O (n + m)$ ，其中 $n$ 是房间的数量， $m$ 是所有房间中的钥匙数量的总数。
空间复杂度： $O (n)$ ，主要为栈的开销。

三、完整代码

# include <iostream>
# include <vector>
using namespace std;class Solution {
private:void dfs(vector<vector<int>>& rooms, vector<bool>& visitRooms, int key) {	// 1、递归输入参数		// 2、递归终止条件 访问过的节点直接返回if (visitRooms[key]) return;// 3、单层递归逻辑	visitRooms[key] = true;for (int i = 0; i < rooms[key].size(); i++) {dfs(rooms, visitRooms, rooms[key][i]);}	}
public:bool canVisitAllRooms(vector<vector<int>>& rooms) {vector<bool> visitRooms = vector<bool>(rooms.size(), false);dfs(rooms, visitRooms, 0);for (int i = 0; i < visitRooms.size(); i++) {if (!visitRooms[i]) return false;}return true;}
};int main() {vector<vector<int>> rooms = { {1}, {2}, {3}, {} };vector<vector<int>> rooms = { {1, 3}, {3, 0, 1}, {2}, {0} };//vector<vector<int>> rooms = { {2, 3}, {}, {2}, {1, 3} };Solution s1;int result = s1.canVisitAllRooms(rooms);cout << result << endl;system("pause");return 0;
}