Ninja Port

Hard
0/120
profile
Contributed by
6 upvotes
Asked in company
Amazon

Problem statement

Ninja is stuck in a city with ‘N’ colonies, and each colony contains ‘K’ houses. Ninja is currently at the house number “sourceHouse” present in the colony with colony number “sourceColony”. He wants to get to the house with house number “destinationHouse” present in the colony with colony number “destinationColony” as fast as possible.

Since Ninja is a Ninja, he also has a special power by which he can teleport from one house to another within the same colony in 1 second. Also, Ninja can travel from the Kth house of the Mth colony to the 1st house of the (M + 1)th colony and also vice versa in the same time.

Additionally, some houses have secret underground paths to other houses, using which Ninja can travel among houses using this path which also takes 1 second.

You are given a list “secretPaths”, each element of this list contains 4 integers. The first two are for the source house of the path “secretSourceHouse” and “secretSourceColony” denoting the source house number and source colony number respectively. The next 2 integers are for the destination house of the path “secretDestinationHouse” and “secretDestinationColony” denoting the destination house number and destination colony number respectively.

Since the underground paths are secret and having too many paths in the same colony could lead the Ninja community getting caught, there are at most ‘P’ underground paths in each colony (which includes incoming and outgoing underground paths).

Note: 
The secret underground paths cannot be used to travel both ways, you can’t travel from destination to source.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains four space-separated integers, ‘N’, ‘K’, ‘S’ and ‘P’ denoting the number of colonies, number of houses in each colony, the number of secret underground paths and the maximum number of underground paths in a colony respectively.

The next line contains four space-separated integers “sourceHouse”, “sourceColony”, “destinationHouse” and “destinationColony” denoting the house number and colony number of Ninja’s initial position and house number and colony number of the destination house respectively.

The next ‘S’ line contains four space-separated integers each denoting the arrays “secretPaths[i]”.
Output Format : 
For each test case, return an integer denoting the minimum time Ninja takes.

Output for each test case will be printed in a new line.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the given functions.
Constraints: 
1 <= T <= 100
1 <= N <= 100
1 <= K <= 10^9
1 <= P <= 50
0 <= S <= (P * N) / 2

Where ‘T’ denotes the number of test cases,
‘N’ denotes the number of colonies,
‘K’ denotes the number of houses in each colony,
‘P’ denotes the maximum number of underground paths in a colony and
‘S’ denotes the number of underground paths.

Time Limit: 1 sec
Sample Input 1 :
1
5 5 1 1
3 1 3 5
1 1 5 5
Sample Output 1:
3

Explanation For Sample Output 1:

The path Ninja follows would be (colony number, house number) = (1, 3) -> (1, 1) -> (5, 5) -> (5, 3).

The first teleport from (1, 3) -> (1, 1) can be performed as both of the houses are in the first colony.

The next transition (1, 1) -> (5, 5) can be done using the underground path and the last one from (5, 5) -> (5, 3) can be done as both the houses are in the fifth colony.
Sample Input 2 :
2
10 5 2 2
2 3 4 10
1 1 5 10
5 8 4 7
7 8 0 0
8 4 6 7
Sample Output 2 :
7
6
Hint

Can we visualize each house as a node in a graph?

Approaches (1)
Breadth First Search

We can initially create a graph with 2 nodes from each colony i.e. the first and last house of each colony would be included in the graph. We also create an edge from the node representing the last node of each colony to the node representing the first node of the next colony, and vice versa.
 

Now, we add into the graph each house that has an outgoing or incoming secret path. We also make edges from the source of the secret underground path to the destination of the secret underground path.
 

For nodes within the same colony, we add an edge between each pair of nodes. 

 

Now that we have a graph ready, we can simply use BFS(Breadth First Search) to find the minimum distance between the nodes representing the source house and the destination house.
 

Algorithm:

  • Create a HashMap “house2node” where we would store all the nodes we want to include in our graph.
  • Start by inserting the initial house of Ninja, and the house where Ninja wants to go i.e. the destination house into “house2Node”.
  • Into “house2node”, insert the first and last house of each colony.
  • Also, for each house used in the secret path, irrespective of whether it is the source or the destination, add it into the “house2node”.
  • Create a graph named “graph” containing all the houses present in ”house2node”.
  • Add edges between nodes from the last house of each colony and the first house of the next colony.
  • Add an edge from the node representing the source house to the node representing the destination house for each secret underground path.
  • For each pair of nodes that represent houses within the same colony, make an edge connecting them.
  • Initialize a queue “bfsQueue” which would be used for traversing the graph and calculating the minimum distance and initialize it with one node index which represents the source house that Ninja is at initially.
  • While there is any node in “bfsQueue”, pop it, iterate through each of its neighbors and add them to the queue if they are not visited. Also, store their distance as distance of current node + 1.
  • If the first node in “bfsQueue” represents the destination house, return the current distance.
Time Complexity

O(P * P * N + S), where ‘N’ denotes the number of colonies, ‘P’ denotes the number of secret paths within each city and ‘S’ denotes the number of secret paths.

 

Note that we create a total of S + N * 2 nodes at max with (2 * (N - 1) + S + P * P * N) edges. Also we iterate through each node and edge once during the BFS, which leads to an overall time complexity of O(S + N * 2 + 2 * (N - 1) + S + P * P * N) which is equivalent to O(P * P * N + S).

Space Complexity

O(P * P * N + S), where ‘N’ denotes the number of colonies, ‘P’ denotes the number of secret paths within each city and ‘S’ denotes the number of secret paths.

 

Note that we create a total of S + N * 2 nodes at max with (2 * (N - 1) + S + P * P * N) edges. Therefore the overall space complexity is O(S + N * 2 + 2 * (N - 1) + S + P * P * N) which is equivalent to O(P * P * N + S).

Code Solution
(100% EXP penalty)
Ninja Port
Full screen
Console