SKIVALL - Ski Valley
The Society of Sport of New Hampshire has decided to build a new attraction in White Mountains. For the first time, the world will see a ski-valley, a ski path that goes downhill then uphill. They believe that skiers can gain enough speed from going down in the first part in order to climb up the second part. To maximize the joy of visitors, they want to find the longest such path.
To simplify calculations, they approximate the mountain terrain with a matrix of square fields and obtain the height of each field from the New Hampshire Geographical Institute. A ski-valley is a sequence of neighboring fields, such that height of fields only decreases along the sequence until some point, and then it only increases until its end. No field appears more than once in a ski-valley. Two fields are neighbors if they share a common edge. The length of a ski-valley is the number of fields in its sequence.
More technically, the terrain is an M x N matrix of fields, where (i, j) denotes a field in the ith row and jth column, and h(i, j) denotes its height. A ski-valley is a sequence (x_{1}, y_{1}), (x_{2}, y_{2}), ..., (x_{l}, y_{l}), such that:
- for any i (1 ≤ i ≤ l-1), either x_{i} = x_{i+1} and |y_{i} - y_{i+1}| = 1, or y_{i} = y_{i+1} and |x_{i} - x_{i+1}| = 1 (neighbors rule)
- if i ≠ j (1 ≤ i, j ≤ l), then either x_{i} ≠ x_{j} or y_{i} ≠ y_{j} (no repeating rule), and
- There exists a k (1 ≤ k ≤ l), such that h(x_{1}, y_{1}) > h(x_{2}, y_{2}) > ... > h(x__{k-1}, y__{k-1}) > h(x_{k}, y_{k}) < h(x__{k+1}, y__{k+1}) < ... < h(x_{l}, y_{l}) (down-up rule).
The length of such ski-valley is l.
They hire you, a reputable programmer, to write a program that will find a ski-valley of maximum length. If there are multiple ski-valleys with the same (maximum) length, you can choose any of them.
Note: Yes, they were not cautious and also allowed a ski-valley to bo only downhill or only uphill, but your job is only to adhere to the specification they gave you!
Input
The first line of the input contains M and N (1 ≤ M, N ≤ 60), respectively, separated by a space character. Each of the next M lines contain N numbers, such that the jth number in the ith line represents h(i, j) (-10^{6} ≤ h(i, j) ≤ 10^{6}). No two fields in the terrain are of the same height. Numbers on a line are separated by a space character.
Output
In the first line of the output, write a single number l_{max}, which is the maximum length of a ski-valley. In the next l_{max} lines write a description of any ski-valley of that length. In each of the lines, write two integers separated by a space character, such that numbers x_{i} and y_{i} in the ith line represent (x_{i}, y_{i}), the ith field in the ski-valley.
Example
Input: 3 4 2 6 7 16 1 4 3 20 9 8 17 12 Output: 9 3 1 3 2 2 2 2 1 1 1 1 2 1 3 1 4 2 4
Added by: | Minilek |
Date: | 2007-10-25 |
Time limit: | 3.817s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | MIT Individual Contest 2007 |