149. Router Reachability on Broadcast and Shutdown Message

Router Reachability on Broadcast and Shutdown Message

You are given a network of routers.

Each router has:

a unique router id
a 2D location (x, y)
a status indicating whether it is WORKING or DEFECTIVE

A special message called Broadcast and Shutdown works as follows:

When a WORKING router receives the message for the first time, it immediately broadcasts the same message to every other WORKING router that lies within the wireless range.
After broadcasting, that router shuts down and can no longer send or receive messages.
A DEFECTIVE router can neither send nor receive the message.

Given the list of routers, the wireless range, a source router id, and a destination router id, determine whether the Broadcast and Shutdown message, when initiated from the source router, will eventually be received by destination router.

Two routers can communicate directly if the Euclidean distance between their coordinates is less than or equal to range.

Return true if the destination router receives the message at any point. Otherwise, return false.

Router Format

To keep the input simple, each router is represented as a string in the following format:

routerId,x,y,status
To make parsing simple, routerId will never contain comma.

Example:

"A,0,0,WORKING"
"B,3,4,DEFECTIVE"

Important Notes

The source router must be WORKING in order to initiate the broadcast.
The destination router is considered reached as soon as it receives the message, even though it will also shut down immediately after rebroadcasting.
A router processes the message at most once.
DEFECTIVE routers must be ignored during message propagation.
No parameter value is null.

Constraints

1 ≤ routers.size() ≤ 10^5
0 ≤ range ≤ 10^6
Each router string has the format routerId,x,y,status
routerId is unique across all routers
-10^6 ≤ x, y ≤ 10^6
status is either WORKING or DEFECTIVE
source and destination are valid router ids present in routers

Method Signatures

Java

boolean canReachDestination(List<String> routers, int range, String source, String destination)

routers contains router descriptions in the format routerId,x,y,status
range is the maximum wireless distance for direct communication
source is the router id where the message starts
destination is the router id to check for reachability

Examples

Example 1

Input

canReachDestination(routers=["A,0,0,WORKING", "B,0,8,WORKING", "C,0,17,WORKING", "D,11,0,WORKING"], range=10, source="A", destination="D")

Output
false

Explanation
Router A can directly reach B. Router B can directly reach C. Router D is not within range of any router that receives the message. So the message never reaches D.

Example 2

Input
canReachDestination(routers=["A,0,0,WORKING", "B,3,4,WORKING", "C,6,8,WORKING"], range=5, source="A", destination="C")

Output
true

Explanation
The distance from A to B is 5, and the distance from B to C is also 5. So the message goes from A to B, then from B to C.

Example 3

Input
canReachDestination(routers=["A,0,0,WORKING", "B,3,4,DEFECTIVE", "C,6,8,WORKING"], range=5, source="A", destination="C")

Output
false

Explanation
Router B is within range of A, but it is DEFECTIVE, so it cannot receive or forward the message. As a result, the message cannot continue to C.

Example 4

Input
canReachDestination(routers=["A,0,0,DEFECTIVE", "B,1,1,WORKING"], range=5, source="A", destination="B")

Output
false

Explanation
The source router A is DEFECTIVE, so the broadcast cannot start.