Google Interview Question
Given a set of N routers in 2-D coordinate, a source router, a destination router. The problem is to find if it is possible to transmit a signal from source to destination under the following constrain-
Each router can transmit messages up to Euclidean distance K.
Each router will shut down after transmitting a message. (In simple words, each router can be used only once.)
N <= 1e5, K <= 10
I have tried to make a graph with nodes as routers and add edges between 2-routers if their Euclidean distance is less than or equal to K. Now, I use normal bfs to see if it is possible to reach the destination. But the problem is The time complexity in this solution is O(N*N). I need a better solution. Does any help please?
