题号：NC24389
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld
题目描述
One of Farmer John's fields is particularly hilly, and he wants to purchase a new tractor to drive around on it. The field is described by an N x N grid of non-negative integer elevations (1 <= N <= 500). A tractor capable of moving from one grid cell to an adjacent cell (one step north, east, south, or west) of height difference D costs exactly D units of money.
FJ would like to pay enough for his tractor so that, starting from some grid cell in his field, he can successfully drive the tractor around to visit at least half the grid cells in the field (if the number of total cells in the field is odd, he wants to visit at least half the cells rounded up). Please help him compute the minimum cost necessary for buying a tractor capable of this task.
输入描述:
* Line 1: The value of N.
* Lines 2..1+N: Each line contains N space-separated non-negative
integers (each at most 1 million) specifying a row of FJ's
field.
输出描述:
* Line 1: The minimum cost of a tractor that is capable of driving
around at least half of FJ's field.
示例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
说明
INPUT DETAILS:
FJ's farm is a 5 x 5 grid. The elevations in the first row are 0, 0, 0, 3,
and 3, and so on.
OUTPUT DETAILS:
A tractor of cost 3 is capable of moving between elevation 0 and elevation
3, so it can visit the block of cells at zero elevation as well as the
block of cells at elevation 3. Together, these represent at least half of
FJ's farm.