Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Honeymoon Hike
Time Limit: 5000MSMemory Limit: 65536K
Total Submissions: 3365Accepted: 1004


Emma is on a hiking trip with Eric, her freshly-married husband, for their honeymoon. They are hiking from one cabin to the next every day. Unfortunately, Eric is not as fit as Emma and is slowly getting tired. Since Emma does not want to start their newly-formed marriage with a serious conflict (and needs somebody to keep her warm in the nights), she decides to plan the next day trips so that they are not so strenuous for Eric.

In the past days, Emma has discovered a surprising fact about her husband. He is not so much tired by the length of their daily trip or the total amount of meters they had to climb. Instead, Eric is tired the more, the bigger the difference between the highest and the lowest point of today’s route becomes. Emma assumes this is due to psychological factors. It just sounds a lot more difficult to climb once from 500 meter to 1,500 meters than to climb from 200 to 400 meters ten times, although you climbed twice as much in the latter case.

Given an altitude map of the terrain, you should help Emma in finding a path that minimizes the difference between its highest and its lowest elevation, so that Eric does not feel as tired. The cabin they start at is located at the top-left corner and their destination is the bottom-right corner of the map. They can move along any of the four major directions but not on a diagonal.


The first line contains the number of scenarios. Each scenario starts with a number n (2 ≤ n ≤ 100), the size of the area. The elevations of the terrain are given as a n × n integer matrix (hi,j) (0 ≤ hi,j ≤ 200) on n lines, where each line contains n space-separated elevations.


The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then, print a single line containing the difference between the highest and the lowest elevation on the optimal path. Terminate the output for the scenario with a blank line.

Sample Input

1 1 3 6 8
1 2 2 5 5
4 4 0 3 3
8 0 2 2 4
4 3 0 3 1

Sample Output

Scenario #1:


TUD Programming Contest 2006, Darmstadt, Germany

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator