MTWALK - Mountain Walking

{assign var="code" value="MTWALK"} {if $par==""} {assign var=par value=$locale} {/if}

{if $par=="vn"} {literal}

Cho một bản đồ kích thước NxN (2 <= N <= 100), mỗi ô mang giá trị là độ cao của ô đó (0 <= độ cao <= 110). Bác John và bò Bessie đang ở ô trên trái (dòng 1, cột 1) và muốn đi đến cabin (dòng N, cột N). Họ có thể đi sang phải, trái, lên trên và xuống dưới nhưng không thể đi theo đường chéo. Hãy giúp bác John và bò Bessie tìm đường đi sao cho chênh lệch giữa điểm cao nhất và thấp nhất trên đường đi là nhỏ nhất.

Dữ liệu

  • Dòng 1: N
  • Dòng 2..N+1: Mỗi dòng chứa N số nguyên, mỗi số cho biết cao độ của một ô.

Kết quả

Một số nguyên là chênh lệch cao độ nhỏ nhất.

Ví dụ

Dữ liệu
5
1 1 3 6 8
1 2 2 5 5
4 4 0 3 3
8 0 2 3 4
4 3 0 2 1

Kết quả
2

{/literal}{elseif ($par=="en" || $par=="")}{literal}

Farmer John and Bessie the cow have embarked on one of those 'active' vacations. They spend entire days walking in the mountains and then, at the end of the day, they tire and return to their vacation cabin.

Since climbing requires a lot of energy and they are already tired, they wish to return to the cabin using a path that has the least difference between its highest and lowest elevations, no matter how long that path is. Help FJ find this easy-to-traverse path.

The map of the mountains is given by an N x N (2 <= N <= 100) matrix of integer elevations (0 <= any elevation <= 110) FJ and Bessie are currently at the upper left position (row 1, column 1) and the cabin is at the lower right (row N, column N). They can travel right, left, toward the top, or toward the bottom of the grid. They can not travel on a diagonal.

Input

  • Line 1: The single integer, N
  • Lines 2..N+1: Each line contains N integers, each of which specifies a square's height. Line 2 contains the first (top) row of the grid; line 3 contains the second row, and so on. The first number on the line corresponds to the first (left) column of the grid, and so on.

Output

An integer that is the minimal height difference on the optimal path.

Example

Input:
5
1 1 3 6 8
1 2 2 5 5
4 4 0 3 3
8 0 2 3 4
4 3 0 2 1

Output:
2

{/literal} {/if}


Được gửi lên bởi:Jimmy
Ngày:2006-02-07
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:USACO 2003 US Open

hide comments
2019-09-14 04:01:01
https://ideone.com/TsQc3F
2019-07-10 18:22:02
bài này cùng 1 code mà code C++ thì AC, cũng code đấy mà viết Java thì time limited
ADMIN set up lại thời gian bài này đi !
2019-07-06 11:27:56
Bài không khó, mà tại mình ngu giống bạn ở dưới :))
2018-10-30 15:50:11
Vietcode là ai thế?
2018-10-30 15:49:14
Duccuto cuc to
2018-08-18 17:22:56
bài ko khó... cơ mà tại mình ngu :)
2018-05-08 12:17:36
anh mạnh 12a2 tự tin 1 đấm ac
2018-05-08 12:17:14
dũng kèn a2 ac 2 nốt nhạc
2018-05-08 12:17:00
qbẩn A2 tự tin ac trong 1 nốt nhạc
2018-05-08 11:45:32
4 lệnh cũng ac
--Huy Túi Bóng
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.