Digger
In a distant and mysterious land known as Quebec, there is a legend of a perfectly rectangular mountain of dimensions AxB metres (1 ≤ A,B ≤ 20000) - legend also says that it's infinitely high. Due to a strange gas phenomenon, N (1 ≤ N ≤ 1000) perfectly rectangular caves (with their sides parallel to those of the mountain) have formed, all at ground level. When viewed as a top-down cross-section, each metre by metre square at ground level can be said to either contain solid rock, be hollow, or contain the treasure. There is only 1 such treasure.
The famous adventurer known only as “Digger” has learnt of this mountain and its treasure, and of course he wants to get to it. Fortunately, he isn't called “Digger” for nothing - he possesses a special machine which can remove all the rock from a metre by metre square (he refuses to tell us where this rock ends up), with the incredible fuel consumption of 1 million gallons per such an operation. Digger can walk freely around any open space, both natural and artificial, but since he's restricted to the ground, the height of the caves doesn't matter. Though Digger is pretty rich, he still wishes to minimize the amount of fuel he uses to reach the treasure.
Digger can start anywhere on the outside of the mountain. Determine the minimum amount of fuel he must use to reach the treasure.
Input
| Line 1: | A, B, and N — respectively, the length of the West and North sides of the mountain (in metres) and the number of caves. |
| Lines 2..N+1: | Y1, X1, Y2 and X2 — the i-th line gives the location of the (i-1)-th cave, where Y1 and Y2 (Y1 ≤ Y2) are the distances of the sides of the cave from the North side of the mountain (in metres), and X1 and X2 (X1 ≤ X2) are the distances from the West side. No two caves will overlap or touch at a corner or side, and all caves will be completely inside the mountain. |
| Lines N+2: | Y and X — the location of the treasure (Y metres from the North side of the mountain, and X metres from the West side). The treasure will lie within one of the caves. |
Output
A single number - the minimum amount of fuel Digger must use to reach the treasure (in millions of gallons).
Sample Input
11 12 3 1 2 1 4 3 5 3 5 5 5 5 6 5 6
Explanation
A bird's-eye-view cross-section of the cave would look like this ('x': solid rock, '.': cave, 'T': treasure):
0 2 4 etc 0 xxxxxxxxxxxx xx...xxxxxxx 2 xxxxxxxxxxxx xxxxx.xxxxxx 4 xxxxxxxxxxxx xxxxx.Txxxxx e xxxxxxxxxxxx t xxxxxxxxxxxx c xxxxxxxxxxxx xxxxxxxxxxxx xxxxxxxxxxxx
Sample Output
4
Explanation
Digger starts by tunnelling to the 1st cave from the North edge of the mountain - this requires 1 million gallons of fuel. He then goes to the 2nd cave, using another 2 million gallons. Finally, he digs down to the 3rd cave, using 1 million gallons of fuel, and then walks to the East to claim the treasure. This is a total of 4 million gallons (1+2+1). One possible set of digging sites is shown below ('D': dig here):
xxDxxxxxxxxx xx...xxxxxxx xxxxDDxxxxxx xxxxx.xxxxxx xxxxxDxxxxxx xxxxx.Txxxxx xxxxxxxxxxxx xxxxxxxxxxxx xxxxxxxxxxxx xxxxxxxxxxxx xxxxxxxxxxxx
All Submissions
Best Solutions
Point Value: 15 (partial)
Time Limit: 1.00s
Memory Limit: 16M
Added: Oct 05, 2008
Author: SourSpinach
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
Anyway, this means that the solution doesn't really have anything to do with how big the caves can get. As such, try treating each cave as a single "position", and figure out how much fuel it takes to get from one cave to another (since they're all rectangular, this isn't hard). That's a start.