MTWALK - Mountain Walking
Tác giả: flashmt
Ngôn ngữ: Pascal
const maxn=105;
dx:array[1..4] of longint=(-1,0,1,0);
dy:array[1..4] of longint=(0,1,0,-1);
var n,max,min,re:longint;
a,d:array[1..maxn,1..maxn] of longint;
q:array[1..maxn*maxn,0..1] of longint;
procedure rf;
var i,j:longint;
begin
min:=111; max:=-1;
readln(n);
for i:=1 to n do
for j:=1 to n do
begin
read(a[i,j]);
if a[i,j]>max then max:=a[i,j];
if a[i,j]<min then min:=a[i,j];
end;
end;
function check(x,y:longint):boolean;
begin
check:=(x>0) and (y>0) and (x<=n) and (y<=n) and (d[x,y]=0);
end;
procedure pr;
var i,j,low,high,num,x,y:longint;
begin
for re:=0 to max-min do
for low:=min to max-re do
begin
high:=low+re;
if (a[1,1]<low) or (a[1,1]>high) then continue;
num:=1; i:=1; q[1,0]:=1; q[1,1]:=1;
fillchar(d,sizeof(d),0);
d[1,1]:=1;
repeat
for j:=1 to 4 do
begin
x:=q[i,0]+dx[j]; y:=q[i,1]+dy[j];
if check(x,y) and (a[x,y]<=high) and (a[x,y]>=low) then
begin
inc(num);
q[num,0]:=x; q[num,1]:=y;
d[x,y]:=1;
end;
end;
inc(i);
until (i>num) or (d[n,n]>0);
if d[n,n]>0 then
begin
writeln(re); halt;
end;
end;
end;
begin
rf;
pr;
end.