841. Keys and Rooms

📘 題目敘述

有 n 間房間，編號從 0 到 n - 1，除了房間 0 以外，所有房間一開始都是鎖住的。

你的目標是造訪所有房間。不過，如果你沒有某個房間的鑰匙，你就不能進入那間上鎖的房間。

當你造訪某個房間時，你可以拿到該房間裡所有的鑰匙。每一把鑰匙都有一個編號，代表它可以打開哪一間房間。

給你一個陣列 rooms，其中 rooms[i] 表示在房間 i 裡能拿到的鑰匙列表。

如果你可以造訪所有房間，回傳 true，否則回傳 false。

條件限制

n == rooms.length
2 <= n <= 1000
0 <= rooms[i].length <= 1000
1 <= sum(rooms[i].length) <= 3000
0 <= rooms[i][j] < n
rooms[i] 裡的所有值都互不相同

🧠 解題思路

我把房間看成一張圖：

每個房間是一個點
房間 i 裡的鑰匙 rooms[i]，代表我從 i 可以走到那些房間

題目問「從房間 0 出發，能不能走到所有點」，本質就是圖的連通性問題。

所以我做 DFS：

我用 allrooms 記錄每個房間有沒有被走到
從 0 開始遞迴拜訪
每到一間房間，就把裡面的鑰匙全部拿來繼續走下去
最後檢查 allrooms 是否全部都變成 true

所有變數

allrooms：大小為 n 的布林陣列，allrooms[i] = true 代表房間 i 已經被造訪過
now：目前 DFS 走到的房間編號

🪜 主要流程步驟

1. 初始化 visited 陣列並從房間 0 開始 DFS

我先用 allrooms.assign(n, false) 把所有房間都設成尚未造訪。

接著呼叫 visit(0, rooms)，代表我從唯一一開始能進去的房間 0 出發。

2. visit(now) 做的事情

每次走到房間 now：

先把 allrooms[now] = true，表示這間房間已經被我進來過
然後把 rooms[now] 裡面的每一把鑰匙都拿來嘗試開門
如果那個房間還沒走過，就遞迴呼叫 visit(那個房間, rooms)

這樣 DFS 會把所有「從 0 出發能到的房間」都標成 true。

3. DFS 結束後檢查是否所有房間都走到

DFS 跑完後，我掃一次 allrooms：

只要有任何一個是 false，代表那間房間永遠拿不到鑰匙進不去，直接回傳 false
否則全部都是 true，回傳 true

⏱️ 複雜度

時間複雜度：O(n + totalKeys) 每個房間最多進一次，每把鑰匙最多看一次。
空間複雜度：O(n) allrooms 需要 n，遞迴深度最壞也可能到 n。

💻 程式碼實作

class Solution {
public:
    vector<bool> allrooms;
    void visit(int now, vector<vector<int>>& rooms) {
        allrooms[now] = true;
        for (int i : rooms[now]) {
            if (!allrooms[i]) {
                visit(i, rooms);
            }
        }
    }
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int n = rooms.size();
        allrooms.assign(n, false);
        visit(0, rooms);
        for (bool j : allrooms) {
            if (!j) {
                return false;
            }
        }
        return true;
    }
};

🔗 題目連結

https://leetcode.com/problems/keys-and-rooms/