PEG Test - December 2014

Problem B: Gift Delivery

Some people are curious of 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 R by C (1 ≤ R, C ≤ 50) two-dimensional grid. The top-left cell of the grid is denoted by coordinates (1, 1) and the bottom-right cell of the grid is denoted by coordinates (R, C). There are N houses at distinct locations on the grid, which Santa has numbered from 1 to N. 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 house in based on how his bag is packed.

Santa starts at the North Pole, located at coordinates (SR, SC). 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 (1, 1) and he travels left, he will arrive at (1, C). Or, if he is located at (R, C) and he travels right, he will end up at (R, 1).

From his research, Santa also knows the secret locations of M wormholes (numbered from 1 to M) 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 tasks 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 Format

Line 1 contains the integers R, C, N, and M.
The next N lines will describe the coordinates of the houses. Namely, the i-th of these lines (for 1 ≤ i ≤ N) will contain a pair of integers describing the row and column of house i.
The next M lines will describe the locations and destinations of the wormholes. Namely, the i-th of these lines (for 1 ≤ i ≤ M) will contain four integers r1, c1, r2, c2. This means that wormhole i is located at (r1, c1), and going into it will teleport Santa to (r2, c2).
The last line of input will contain two space-separated integers SR and SC, representing the coordinates of the North Pole.

Output Format

The output should contain a single integer representing the length of shortest path it takes for Santa to travel to all N 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 3 houses (represented by the characters 1 through 3) and 2 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 1, Santa's path is: down → left through wormhole A → left onto house 1. (3 steps)
To get from house 1 to house 2, Santa's path is: left (this wraps him back around from the right side of the map) → down onto house 2. (2 steps)
To get from house 2 to house 3, 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 3 (2 steps)
To get from house 3 back to the North Pole, Santa's path can be: left → left → left → left → up. (5 steps)
Therefore, the total distance is 3 + 2 + 2 + 5 = 12.

All Submissions
Best Solutions


Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Dec 13, 2014
Author: Alex

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...