编程介的小学生 2017-08-29 03:52 采纳率: 0.2%
浏览 677
已采纳

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 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.

Output

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
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

展开全部

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-09-12 16:29
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
编辑
预览

报告相同问题?

悬赏问题

  • ¥15 python 用Dorc包报错,我的写法和网上教的是一样的但是它显示无效参数,是什么问题
  • ¥15 指定IP电脑的访问设置
  • ¥30 matlab ode45 未发现警告,但是运行出错
  • ¥15 vscode platformio
  • ¥15 代写uni代码,app唤醒
  • ¥15 全志t113i启动qt应用程序提示internal error
  • ¥15 ensp可以看看嘛.
  • ¥80 51单片机C语言代码解决单片机为AT89C52是清翔单片机
  • ¥60 优博讯DT50高通安卓11系统刷完机自动进去fastboot模式
  • ¥15 minist数字识别
手机看
程序员都在用的中文IT技术交流社区

程序员都在用的中文IT技术交流社区

专业的中文 IT 技术社区,与千万技术人共成长

专业的中文 IT 技术社区,与千万技术人共成长

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

客服 返回
顶部