MTWALK - Mountain Walking
Tác giả: ladpro98
Ngôn ngữ: Pascal
program mtwalk;
uses math;
type e=record
x,y:longint;
end;
const fi='';
maxn=123;
dx:array[1..4] of longint = (0,0,1,-1);
dy:array[1..4] of longint = (1,-1,0,0);
var a:array[1..maxn,1..maxn] of longint;
avail:array[1..maxn,1..maxn] of boolean;
q:array[1..maxn*maxn] of e;
res,n,maxA,minA:longint;
procedure input;
var inp:text;
i,j:longint;
begin
assign(inp,fi);reset(inp);
readln(inp,n);
minA:=123456789;
for i:=1 to n do
begin
for j:=1 to n do
begin
read(inp,a[i,j]);
maxA:=max(maxA,a[i,j]);
minA:=min(minA,a[i,j]);
end;
readln(inp);
end;
close(inp);
end;
function inBound(i,j:longint):boolean;
begin
exit((1<=i) and (i<=n) and (1<=j) and (j<=n));
end;
function bfs(low,high:longint):boolean;
var l,r,i,j,x,y:longint;
u:e;
begin
l:=1;r:=1;
q[1].x:=1;
q[1].y:=1;
for i:=1 to n do
for j:=1 to n do
avail[i,j]:=true;
avail[1,1]:=false;
while l<=r do
begin
u:=q[l];inc(l);
for i:=1 to 4 do
begin
x:=u.x+dx[i];
y:=u.y+dy[i];
if inBound(x,y) and avail[x,y] and (low<=a[x,y]) and (a[x,y]<=high) then
begin
avail[x,y]:=false;
inc(r);
q[r].x:=x;
q[r].y:=y;
if (x=n) and (y=n) then exit(true);
end;
end;
end;
exit(false);
end;
procedure process;
var minV,l,r,m:longint;
begin
res:=123456789;
for minV:=a[1,1] downto minA do
begin
l:=minV;r:=maxA;
while l<=r do
begin
m:=(l+r) div 2;
if bfs(minV,m) then
begin
res:=min(res,m-minV);
r:=m-1;
end
else l:=m+1;
end;
end;
end;
begin
input;
process;
write(res);
end.