A higher resolution is required to access the IDE
- 66
Learning Opportunities
This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.
Statement
Goal
Story:Help the fellowship! They are trapped in the mines of Moria, with orcs closing in from all sides. Their only hope is Gandalf’s wizardry. Gandalf can create portals through which they can quickly travel from one spot to another. However portals can be opened in limited spots only, and in a limited number of ways. Your program must print the path they should follow to be safely out.
--------------------------------------------------- xxx ---------------------------------------------------
Rules:
The Spots will be
You will be given the
You will be given the
You will also be given the
(note: the paths are double sided. this means that if a path is possible from spot 2 to spot 5, then it is possible to go from 2 to 5, as also from 5 to 2)
--------------------------------------------------- xxx ---------------------------------------------------
The Problem:
Your algorithm should display the sequence of the spots in order of how the fellowship go in order to reach the end fastest, and safely.
(note: the fellowship can travel from one spot to another along the
You will be given the index of the
--------------------------------------------------- xxx ---------------------------------------------------
Note:
1. For every move of the fellowship, each orc can move by a distance of 1. If you need N moves to reach a spot, and distance from the starting point of an orc to that spot is ≤ N, you cannot go there or you might be killed.
For example, if spot 2 and spot 5 are connected by a path, and coordinates of 2 is (1,0) and 5 is (2,2), and an orc is present at (1,2), then the fellowship cannot go from spot 2 to spot 5, as time taken by the fellowship is 1 UNIT, and distance moved by the orc in 1 unit time is 1 UNIT ((2,1) and (2,2) are separated by distance 1 UNIT).
2. The fellowship can only move along the paths from one spot to another.
For example, if spot 2 and spot 5 are connected by a path, and coordinates of 2 is (1,0) and 5 is (2,2), then from 2 the fellowship can move only to 5, and not to any random spot {say (1,2)} [i.e. they can only move to a spot, which is connected] .
3. Distances are calculated by the distance formula: dist = sqrt( (p1.x-p2.x)^2 + (p1.y-p2.y)^2 ) (i.e. distances are Pythagorean)
Input
Line 1: an integer N denoting the number of spots
Line 2: an integer M denoting the number of orcs
Line 3: an integer L denoting the number of portals
Next N lines: 2 integers XS, YS, the coordinates of the spots
Next M lines: 2 integers XO, YO, the coordinates of the orcs
Next L lines: 2 integers N1, N2, the indexes of 2 spots of a path forming a portal
Next line: an integer S denoting the spot from which the fellowship start (the index)
Next line: an integer E denoting the spot where the fellowship need to reach (the index)
Line 2: an integer M denoting the number of orcs
Line 3: an integer L denoting the number of portals
Next N lines: 2 integers XS, YS, the coordinates of the spots
Next M lines: 2 integers XO, YO, the coordinates of the orcs
Next L lines: 2 integers N1, N2, the indexes of 2 spots of a path forming a portal
Next line: an integer S denoting the spot from which the fellowship start (the index)
Next line: an integer E denoting the spot where the fellowship need to reach (the index)
Output
Your output should consist of one line of integers separated by spaces, denoting the indexes of the spots to which the fellowship go. (in order)
If it is not possible to reach the end, print a single String IMPOSSIBLE
If it is not possible to reach the end, print a single String IMPOSSIBLE
Constraints
1 ≤ N, L ≤ 100
0 ≤ M ≤ 100
0 ≤ M ≤ 100
Example
Input
4 1 4 1 1 2 0 2 2 3 1 1 2 0 1 0 2 1 3 2 3 0 3
Output
0 1 3
A higher resolution is required to access the IDE