PEG Test - December 2014
Some people are curious about how Santa is always able to deliver all of
his presents on time on Christmas Eve. Just how is it possible that St.
Nick can travel such great distances across the world to deliver
billions of presents? Well, the reality is that there will always be
skeptics, doubters, and cynics. What these people don't know is that
Santa was once the world's most ingenious relative physicist. After
St. Dr. Nicholas finalized his study of using wormholes in the
space-time continuum to time travel/teleport, he concluded that the
world was most certainly not ready for his findings. Instead of
publishing it, he ultimately decided to keep the momentous discovery to
himself and use it for good – that is, delivering Christmas joy to every
girl and boy!
Every Christmas Eve, Santa plans his route on a map of the world. For the sake of simplicity, the world can be thought of as an by two-dimensional grid. The top-left cell of the grid is denoted by coordinates and the bottom-right cell of the grid is denoted by coordinates . There are houses at distinct locations on the grid, which Santa has numbered from to . Santa's packed the gifts in his bag in a specific way. Since there are so many gifts, he can't be digging through his giant bag to find a particular gift whenever he arrives at houses. That'll take too long. Instead, he has a preplanned order to visit the houses based on how his bag is packed.
Santa starts at the North Pole, located at coordinates . At any given time, Santa may fly to the cell above, below, left, or right of his current location. Remember that the Earth is a sphere, and the map is just a 2D representation, so flying off the border of the map is allowed! It just means that Santa will wrap back around from the other side of the map. For example, if he is located at and he travels left, he will arrive at . Or, if he is located at and he travels right, he will end up at .
From his research, Santa also knows the secret locations of wormholes (numbered from to ) that will each take him from the location of the wormhole (guaranteed not to be a house or the North Pole) to another given place in the world. Any given cell on the grid is either a house, a wormhole opening, or neither. When he flies into a wormhole, he will be instantly teleported to whatever location the wormhole points to (this may be a house or an empty cell, but not another wormhole). Being teleported by a wormhole does not count towards Santa's distance traveled. Santa may fly over a house, even if it's not the house he's currently trying to deliver to.
Now, your task is to determine the shortest number of units that Santa will need to travel to deliver gifts to all houses in the order he has specified, and then return to the North Pole.
Input Specification
Line will contain the integers , , , and .
The next lines will describe the coordinates of the houses. Namely,
the -th of these lines (for ) will contain a pair of
integers describing the row and column of house .
The next lines will describe the locations and destinations of the
wormholes. Namely, the -th of these lines (for ) will
contain four integers . This means
that wormhole is located at , and going into it
will teleport Santa to .
The last line of input will contain two space-separated integers
and , representing the coordinates of the North Pole.
Output Specification
The output should contain a single integer representing the length of the shortest path it takes for Santa to travel to all houses in the specified order and return to the North Pole.
Sample Input
5 10 3 2
4 1
5 10
2 10
2 5 4 2
5 5 1 10
1 6
Sample Output
12
Explanation
The map of the world is as follows. There are houses (represented by
the characters 1
through 3
) and wormholes (we'll call these A
and B
, where their destinations are marked in the corresponding
lowercase). N
represents the North Pole.
.....N...b
....A....3
..........
1a........
....B....2
To get from the North Pole to house , Santa's path is: down left
through wormhole A
left onto house . ( steps)
To get from house to house , Santa's path is: left (this wraps him
back around from the right side of the map) down onto house . (
steps)
To get from house to house , Santa's path is: down (this wraps him
back up to the destination of wormhole B
. However, since b
is only a
destination, nothing happens) down onto house ( steps)
To get from house back to the North Pole, Santa's path can be: left
left left left up. ( steps)
Therefore, the total distance is .
Comments