Disaster Relief Route Tracker
The emergency logistics bureau needs rapid insight into how far supply convoys can travel when floods block certain relief roads. Every shelter is numbered from 0 to n - 1, and the bureau keeps an inventory of roads that allow trucks to drive between shelters in two directions. Once a convoy sets out from a staging shelter, the team drives along open roads, sharing updates and delivering aid to each shelter they can reach. Roads that are submerged or otherwise impassable cannot be used, and convoys avoid placing resources at a blocked shelter.
Write a function that takes the number of shelters n, a list of roads roads, the staging shelter start, and a set blocked_shelters indicating which locations are currently inaccessible. Each road is described by [u, v], signifying that trucks can travel between shelters u and v, so long as both endpoints are open. The road list may include duplicate entries, repeated directions, or a self-loop representing a staging circle. The staging shelter is never blocked. Convoys skip any road leading into a blocked shelter and do not count that place in the final tally.
The result should be the number of open shelters reached by the convoy, including the staging point. Blocked shelters are excluded even if alternative paths exist. If the convoy cannot leave start, the total is 1. When all routes are open, the answer equals the size of the connected component that contains the staging location. Ignore duplicate roads while ensuring every unique open shelter that the convoy can visit is counted exactly once.
Example 1:
Input: n = 6, roads = [[0,1],[1,2],[2,3],[3,4],[1,5]], start = 1, blocked_shelters = [4]
Output: 5
Explanation: The convoy reaches shelters 1, 0, 2, 3, and 5 while skipping the blocked shelter 4.
Example 2:
Input: n = 5, roads = [[0,1],[1,2],[2,3],[3,4]], start = 0, blocked_shelters = [2]
Output: 2
Explanation: The convoy can only deliver to shelters 0 and 1 before encountering a blocked location.
Example 3:
Input: n = 4, roads = [], start = 2, blocked_shelters = []
Output: 1
Explanation: With no roads, only the staging shelter receives supplies.
Related Problems
No related problems found
Comments (0)
Join the Discussion
Share your thoughts, ask questions, or help others with this problem.
