## Editorial for Mountain Walking

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

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;
for i:=1 to n do
for j:=1 to n do
begin
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.


#### Code mẫu của happyboy99x

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define N 105

int vst[N][N], a[N][N], n, mn, mx;
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

bool dfs(int u, int v) {
//printf( "%d %d %d %d %d\n", u, v, min, max, lim );
vst[u][v] = 1; if( u == n - 1 && v == n-1 ) return 1;
for(int i = 0; i < 4; ++i) {
int x = u + dx[i], y = v + dy[i];
if( x >= 0 && y >= 0 && x < n && y < n && !vst[x][y] && a[x][y] >= mn && a[x][y] <= mx )
if(dfs(x,y)) return 1;
}
return 0;
}

int main() {
//    freopen("input.txt", "r", stdin);
scanf( "%d", &n );
for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) scanf("%d",&a[i][j]);
int res = (int) 1e9;
for(mn = 0; mn <= a[0][0]; ++mn) {
int L = 0, H = 120;
while( L <= H ) {
int mid = (L+H)>>1;
mx = mn+mid;
memset(vst, 0, sizeof vst);
bool ok = dfs(0,0);
//printf( "%d %d %d\n", mn, mx, ok );
if( L == H ) {
if( !ok ) L = 1000000000;
break;
}
if(ok) H = mid;
else L = mid + 1;
}
res = min(res, L);
}
printf( "%d\n", res );
return 0;
}


#### Code mẫu của ladpro98

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);
minA:=123456789;
for i:=1 to n do
begin
for j:=1 to n do
begin
maxA:=max(maxA,a[i,j]);
minA:=min(minA,a[i,j]);
end;
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.


#### Code mẫu của RR

{$R-,Q-} {$inline on}
program MTWALK;
const
FINP='';
FOUT='';
MAXN=101;
oo=110;
di:array[1..4] of shortint=(0,0,-1,1);
dj:array[1..4] of shortint=(-1,1,0,0);
var
a:array[1..MAXN,1..MAXN] of integer;
xet:array[1..MAXN,1..MAXN] of byte;
qu,qv:array[1..MAXN*MAXN] of integer;
n,kq:integer;
procedure inp; inline;
var
f:text;
i,j:integer;
begin
assign(f,FINP); reset(f);
for i:=1 to n do
for j:=1 to n do
close(f);
end;
procedure ans; inline;
var
f:text;
begin
assign(f,FOUT); rewrite(f);
writeln(f,kq);
close(f);
end;
function bfs(min,max:integer):boolean; inline;
var
first,last,u,v,uu,vv,h:longint;
begin
fillchar(xet,sizeof(xet),0);
first:=1; last:=1; qu[1]:=1; qv[1]:=1; xet[1,1]:=1;
bfs:=true;
while first<=last do
begin
u:=qu[first]; v:=qv[first]; inc(first);
if (u=n) and (v=n) then exit;
for h:=1 to 4 do
begin
uu:=u+di[h]; vv:=v+dj[h];
if (uu>0) and (uu<=n) and (vv>0) and (vv<=n) then
if (xet[uu,vv]=0) and (a[uu,vv]>=min) and (a[uu,vv]<=max) then
begin
xet[uu,vv]:=1;
inc(last); qu[last]:=uu; qv[last]:=vv;
if (uu=n) and (vv=n) then exit;
end;
end;
end;
bfs:=false;
end;
function ok(x:integer):boolean; inline;
var
i,g:integer;
begin
if oo-x>a[1,1] then g:=a[1,1] else g:=oo-x;
for i:=0 to g do
if bfs(i,i+x) then exit(true);
exit(false);
end;
procedure solve; inline;
var
l,r,mid:integer;
begin
l:=0; r:=oo;
repeat
mid:=(l+r) div 2;
if ok(mid) then r:=mid else l:=mid;
until r-l<=1;
if ok(l) then kq:=l else kq:=r;
end;
begin
inp;
solve;
ans;
end.


#### Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>

int a[101][101],flag[101][101],n;

bool tm(int a,int b)
{
if(a>=1 && a<=n && b>=1 && b<=n && flag[a][b]==0)
return true;
return false;
}

void duyet(int x,int y,int min,int max)
{
if(a[x][y]>=min && a[x][y]<=max)
{
flag[x][y]=1;
if(x == n && y==n);
else
{
if(tm(x+1,y)) duyet(x+1,y,min,max);
if(tm(x-1,y)) duyet(x-1,y,min,max);
if(tm(x,y+1)) duyet(x,y+1,min,max);
if(tm(x,y-1)) duyet(x,y-1,min,max);
}
}
}

bool find_path(int x)
{
int fl = 0;
for(int i = 0;i<=110-x;i++)
{
for(int j = 1;j<=n;j++)
for(int k = 1;k<=n;k++)
flag[j][k] = 0;
flag[1][1]=1;
duyet(1,1,i,i+x);
if(flag[n][n]==1)
{
fl=1;
break;
}
}
if(fl==1) return true;
return false;
}

int main()
{
// freopen("MTWALK.in","r",stdin);
scanf("%d",&n);
for(int i = 1;i<=n;i++)
for(int j = 1;j<=n;j++)
scanf("%d",&a[i][j]);
int u = 0, v = 111;
while(v-u>1)
{
int r = (u+v)/2;
if(find_path(r)) v = r;
else u = r;
}
if(find_path(u))
printf("%d",u);
else printf("%d",v);
//getch();
}


#### Code mẫu của ll931110

Program MTWALK;
Const
input  = '';
output = '';
maxn = 100;
dx: array[1..4] of integer = (-1,0,1,0);
dy: array[1..4] of integer = (0,1,0,-1);
Var
n,inf,sup: integer;
a: array[1..maxn,1..maxn] of integer;
d: array[0..maxn + 1,0..maxn + 1] of boolean;

Procedure init;
Var
f: text;
i,j: integer;
Begin
Assign(f, input);
Reset(f);

For i:= 1 to n do
For j:= 1 to n do read(f, a[i,j]);

Close(f);
End;

Procedure DFS(x,y: integer);
Var
i,x1,y1: integer;
Begin
For i:= 1 to 4 do
Begin
x1:= x + dx[i];
y1:= y + dy[i];

If d[x1,y1] and (inf <= a[x1,y1]) and (a[x1,y1] <= sup) then
Begin
d[x1,y1]:= false;
If (x1 = n) and (y1 = n) then exit;
DFS(x1,y1);
End;

If not d[n,n] then exit;
End;
End;

Procedure solve;
Var
len,i,j,p,q: integer;
f: text;
Begin
For len:= 0 to 110 do
Begin
p:= a[1,1] - len;
If p < 0 then p:= 0;

For q:= p to a[1,1] do
Begin
inf:= q;
sup:= q + len;

Fillchar(d, sizeof(d), false);
For i:= 1 to n do
For j:= 1 to n do d[i,j]:= true;

DFS(1,1);
If not d[n,n] then
Begin
Assign(f, output);
Rewrite(f);
Writeln(f, len);
Close(f);

exit;
End;
End;
End;
End;

Begin
init;
solve;
End.


#### Code mẫu của skyvn97

#include<stdio.h>
//#include<conio.h>
#define MAX   111
int h[MAX][MAX];
int c[MAX][MAX];
int n;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int maxh,minh;
void init(void)
{
scanf("%d",&n);
int i,j;
maxh=0;
minh=1e5;
for (i=1;i<=n;i=i+1)
for (j=1;j<=n;j=j+1)
{
scanf("%d",&h[i][j]);
if (h[i][j]>maxh) maxh=h[i][j];
if (h[i][j]<minh) minh=h[i][j];
}
for (i=0;i<=n+1;i=i+1)
{
c[0][i]=2;
c[i][0]=2;
c[n+1][i]=2;
c[i][n+1]=2;
}
}
void DFS(int x,int y)
{
int i;
c[x][y]=1;
for (i=0;i<=3;i=i+1)
if (c[x+dx[i]][y+dy[i]]==0)
{
c[x+dx[i]][y+dy[i]]=1;
DFS(x+dx[i],y+dy[i]);
}
}
bool moveable(int min,int max)
{
int i,j;
for (i=1;i<=n;i=i+1)
for (j=1;j<=n;j=j+1)
{
if ((h[i][j]<min) || (h[i][j]>max))
c[i][j]=2;
else c[i][j]=0;
}
if (c[1][1]>0) return (false);
if (c[n][n]>0) return (false);
c[1][1]=1;
DFS(1,1);
if(c[n][n]==0)  return (false);
return(true);
}
bool move(int d)
{
int i;
for (i=minh;i+d<=maxh;i=i+1)
if (moveable(i,i+d)) return (true);
return (false);
}
void process(void)
{
int l=0;
int r=maxh-minh;
int m;
while (l<=r)
{
if (l==r)
{
printf("%d",r);
return;
}
if (r-l==1)
{
if (move(l))
{
printf("%d",l);
return;
}
printf("%d",r);
return;
}
m=(l+r)/2;
if (move(m)) r=m;
else l=m+1;
}
}
int main(void)
{
//freopen("tmp.txt","r",stdin);
init();
process();
//getch();
}


#### Code mẫu của khuc_tuan

#include <iostream>
using namespace std;

int a[111][111];
bool vs[111][111];
int n;

void dfs(int i, int j, int st, int en) {
if(i<0 || i>=n || j<0 || j>=n) return;
if(vs[i][j]) return;
if(a[i][j] < st || a[i][j] > en) return;
vs[i][j] = true;
for(int dx=-1;dx<=1;++dx) for(int dy=-1;dy<=1;++dy) if((dx==0) ^ (dy==0)) dfs(i+dx,j+dy,st,en);
}

int main() {
scanf("%d", &n);
for(int i=0;i<n;++i) for(int j=0;j<n;++j) scanf("%d", a[i]+j);
int left = 0, right = 111;
while(left<right) {
int mid = (left+right) / 2;
bool ok = false;
for(int st=0;st<=111;++st) {
memset( vs, 0, sizeof(vs));
dfs(0,0,st,st+mid);
if(vs[n-1][n-1]) {
ok = true;
break;
}
}
if (ok) right = mid;
else left = mid + 1;
}
printf("%d\n", left);
return 0;
}