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.

Download