Tractor (Silver)
실버 II의견: 0
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.
The minimum cost of a tractor that is capable of driving around at least half of FJ's field.
tractor.intractor.out5
0 0 0 3 3
0 0 0 0 3
0 9 9 3 3
9 9 9 3 3
9 9 9 9 33Output details: A tractor of cost 3 can move between elevation 0 and elevation 3, visiting the zero block and the elevation-3 block, together at least half the farm.
riseoj 작성
출처 올림피아드 > USACO > 2012-2013 > February > Silver
평가 및 의견
Tractor (Silver)
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Tractor (Silver)