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;
     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.

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);
        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.

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);
  readln(f,n);
  for i:=1 to n do
  for j:=1 to n do
    read(f,a[i,j]);
  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);

  Readln(f, n);
  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;   
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.