DMOPC '14 Contest 4 P3 - Golden Lily - Olympiads Online Judge

DMOPC '14 Contest 4 P3 - Golden Lily

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 128M

Author:

Problem types

As the Japanese imperial army looted Southeast Asia during the 1930s, Emperor Hirohito launched an organization called Kin no yuri, "Golden Lily", aimed at recovering and hiding the plunder, which consisted mainly of gold. A significant portion was hidden deep within caves in the Philippines such that it would remain safe and be used to finance Japan's military ambitions (Johnson, C. The Looting of Asia).

The war is now over and American intelligence agents have obtained the locations of the hiding spots. Beneath lies a massive amount of gold and treasure worth billions and since no one knows about it, could be used to finance a limitless number of causes.

Using advanced scanning technology, the exact location of the treasure has been found and is represented by a coordinate. In addition, the density for every unit of volume in the ground below has been determined and represents the average density of the material they will have to drill through, which can range from sediments and soil to solid rock.

Given the densities of the ground below as a 2-dimensional grid with the x-axis representing the ground and the y-axis representing the depth into the ground, determine the minimal amount of drilling that will be performed. Note that you start at the top-left corner $(0, 0)$ ~(0, 0)~ and that you cannot drill upwards or diagonally; only to the left, right, or down.

Input Specification

The first line of input will consist of two integers, $L$ ~L~ and $D$ ~D~ $(1 \le L, D \le 1\,000)$ ~(1 \le L, D \le 1\,000)~, separated by a space representing the length (x-axis) and the depth (y-axis).

The next $D$ ~D~ lines of input will contain $L$ ~L~ space-separated integers. Each of these integers $i$ ~i~ $(1 \le i \le 100)$ ~(1 \le i \le 100)~ represents the density of the ground at that point.

The last line of input will consist of two integers each separated by a space representing the coordinate $(length, depth)$ ~(length, depth)~ of the gold.

Output Specification

The only line of output should contain the minimal amount of drilling that will be required — that is, minimize the sum of the spaces travelled to reach the gold.

Sample Input

Sample Output

Explanation for Sample Output

The amount of drilling required to reach (0, 1) is 5 while to reach (1, 0) the value is 4. The gold is located adjacent to these two points, and since it has a density of 3, the output will be 7.

Comments

1

Evanhyd commented on Jan. 28, 2021, 4:04 a.m.

WTH inverted X and Y just to troll us.

5

Oppenheimer commented on Feb. 10, 2015, 11:09 p.m.

The amount of drilling required to reach (0, 1) is 5 while to reach (1, 0) the value is 4. How do you know this????

2

Sentient commented on Feb. 10, 2015, 11:14 p.m. ← edit 2 →

The problem statement describes the input as representing a grid => (length, depth). To clarify: (0,0) = 1 (0,1) = 4 The sum of densities to reach (0,1) is 5 (go through 0,0 and 0,1). (0,0) = 1 (1,0) = 3 The sum of densities to reach (1,0) is 4 (go through 0,0 and 1,0) What's the cheapest way of reaching (1,1)?

3

bobhob314 commented on Feb. 11, 2015, 2:39 a.m.

Hey Oppy ;). I had the same problem.

The part that might be confusing is that whereas usually points are defined as (row, col), the points here are defined as (col, row) in the input (that is, where row is a depth and col is a vertically-longer rectangle).