Problem E
Millionaire Madness
A close friend of yours, a duck with financial problems, has requested your help with a matter that will help him pay off his debts. He is the nephew of an extremely wealthy duck, who has a large vault, filled with mountains of coins. This wealthy duck has a certain coin in his possession which has a lot of sentimental value to him. Usually, it is kept under a protective glass dome on a velvet cushion.
However, during a recent relocating of the coins in the vault, the special coin was accidentally moved into the vault, leading to an extremely stressful situation for your friend’s uncle. Luckily, the coin has recently been located. Unfortunately, it is completely opposite to the entrance to the vault, and due to the mountains of coins inside the vault, actually reaching the coin is no simple task.
He is therefore willing to pay your friend to retrieve this coin, provided that he brings his own equipment to scale the mountains of coins. Your friend has decided he will bring a ladder, but he is still uncertain about its length. While a longer ladder means that he can scale higher cliffs, it also costs more money. He therefore wants to buy the shortest ladder such that he can reach the special coin, so that he has the largest amount of money left to pay off his debts.
The vault can be represented as a rectangular grid of stacks
of coins of various heights (in meters), with the entrance at
the north west corner (the first height in the input, the
entrance to the vault is at this height as well) and the
special coin at the south east corner (the last height in the
input). Your avian companion has figured out the height of the
coins in each of these squares. From a stack of coins he can
attempt to climb up or jump down to the stack immediately
north, west, south or east of it. Because your friend cannot
jump or fly (he is a very special kind of duck that even wears
clothes), successfully performing a climb of
Input
The first line contains two integers: the length
The following
Output
Output a single line containing a single integer: the length in meters of the shortest ladder that allows you to get from the north west corner to the south east corner.
Sample Input 1 | Sample Output 1 |
---|---|
3 3 1 2 3 6 5 4 7 8 9 |
1 |
Sample Input 2 | Sample Output 2 |
---|---|
1 4 4 3 2 1 |
0 |
Sample Input 3 | Sample Output 3 |
---|---|
7 5 10 11 12 13 14 11 20 16 17 16 12 10 18 21 24 14 10 14 14 22 16 18 20 20 25 25 24 22 10 25 26 27 28 21 25 |
3 |