Hướng dẫn giải của Mountain Walking
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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; }
Bình luận