文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 DFS
    • 2.2 BFS

1. 題目

有 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 號房間。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/keys-and-rooms
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

2.1 DFS

class Solution { public:bool canVisitAllRooms(vector<vector<int>>& rooms) {bool visited[rooms.size()] = {false};dfs(visited, rooms, 0);for(int i = 0; i < rooms.size(); ++i){if(visited[i] == false)return false;}return true;}void dfs(bool *visited, vector<vector<int>> &rooms, int i){visited[i] = true;for(int key = 0; key < rooms[i].size(); ++key){if(!visited[rooms[i][key]])dfs(visited, rooms, rooms[i][key]);}} };

2.2 BFS

class Solution { public:bool canVisitAllRooms(vector<vector<int>>& rooms) {bool visited[rooms.size()] = {false};queue<int> q;q.push(0);visited[0] = true;int key, roomID, i;while(!q.empty()){roomID = q.front();q.pop();for(i = 0; i < rooms[roomID].size(); ++i){key = rooms[roomID][i];if(!visited[key]){q.push(key);visited[key] = true;}}}for(int i = 0; i < rooms.size(); ++i){if(visited[i] == false)return false;}return true;} };

總結

以上是生活随笔為你收集整理的LeetCode 841. 钥匙和房间（DFS/BFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。