← 返回题目
题库练习 拖拉机
← 上一题 下一题 →

A2782 | 拖拉机

来源USACO / 2013
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

FJ有块农田太崎岖了，他要买一辆新拖拉机才能在这里巡视。这块农田由N x N个格子的非负整数表示高度(1<=N<=500)。拖拉机从当前格子走到相邻格子（东、南、西、北四个方向）的代价为高度差D，则FJ驶过这两个格子的拖拉机最少也要值D块钱。

FJ愿意花足够的钱买一辆新的拖拉机使得他能以最小的高度差走遍所有格子的一半(如果格子总数是奇数，那么一半的值为四舍五入的值)。因为FJ很懒，所以他找到你帮他编程计算他最小需要花多少钱买到符合这些要求的拖拉机。

输入格式

第一行为一个整数N

第2到N+1行每行包含N个非负整数（不超过1,000,000），表示当前格子的高度。

输出格式

共一行，表示FJ买拖拉机要花的最小价钱。

输入输出样例

输入 #1
5 
0 0 0 3 3 
0 0 0 0 3 
0 9 9 3 3 
9 9 9 3 3 
9 9 9 9 3
输出 #1
3
C++ 编辑器
输入
输出