TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1183
  • 题目
  • P1183何老板玩滑雪板
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    又到了滑雪的季节。何老板背着滑雪板来到了阿尔卑斯山。
    阿尔卑斯山的地势图可以看作一个N*N的数字矩阵,由1-N^2的数字组成(每个数字出现且仅出现一次),这些数字表示每个地点的地势高低。何老板的出发点在最高的山顶处,并且每次何老板可以从当前所在的位置用滑雪板跳跃到任何一个比当前地点高度低的位置,假设何老板该次跳跃从坐标(x1,y1)跳到了坐标(x2,y2),则这次跳跃的精彩度定义为v=(|x1-x2|+|y1-y2|)^2。何老板想找一条路径就是从山顶不断跳跃直到山底(高度最低点)的精彩度总和最高的路径,而现在我们想要知道的是这个最高的精彩度总和是多少。

    输入格式

    第一行包括一个整数n(n<=50)表示地图的长宽。
    接下来n行每行包括n个数表示每个地点的高度。

    输出格式

    一个整数ans,表示从山顶到山底最高精彩度总和

    样例输入

    2
    3 2 
    1 4

    样例输出

    9

    提示

    最优路径为4->3->2->1,得分为4+1+4=9。