Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Honeymoon Hike
Description 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. Input The first line contains the number of scenarios. Each scenario starts with a number _{,j}) (0 ≤ h_{i}_{,j} ≤ 200) on n lines, where each line contains n space-separated elevations.Output The output for every scenario begins with a line containing “ Sample Input 1 5 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: 3 Source TUD Programming Contest 2006, Darmstadt, Germany |

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

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator