Inspect Every Room
HardBit Manipulation
Problem
A safety inspector must visit every room of a building. The building is an undirected connected graph: corridors[r] lists the rooms directly reachable from room r. Walking one corridor takes one step.
The inspector may start in any room, end in any room and pass through rooms and corridors as often as needed. Return the minimum number of steps needed to have visited every room at least once.
Example 1
- Input:
- corridors = [[1, 2, 3], [0], [0], [0]]
- Output:
- 4
1 → 0 → 2 → 0 → 3.
Example 2
- Input:
- corridors = [[1], [0, 2], [1, 3], [2]]
- Output:
- 3
A straight line walked from one end.
Example 3
- Input:
- corridors = [[]]
- Output:
- 0
Constraints
- 1 ≤ n = corridors.length ≤ 12
- The graph is undirected, connected and has no self-loops or duplicate corridors.
Hint
Show the first hint
Where you are is not enough to describe progress. What else must a state remember?
Walkthrough
How to approach it
01Clarify before coding
- Can rooms be revisited? Yes, as often as needed; only the step count matters.
- Must the walk return to the start? No, it can end anywhere.
- How many rooms? At most 12, which hints at 2^n states.
02Brute force
Try every order of rooms, joining consecutive rooms by shortest paths, and keep the cheapest order.
Cost: O(n! · n) after all-pairs shortest paths: 12! ≈ 4.8 · 10^8 orders. Too slow.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.