Nguồn đề bài http://vn.spoj.com/problems/MTWALK/
Nội dung bài viết
1. Đề bài MTWALK spoj
Cho một bản đồ kích thước NxN (2 <= N <= 100), mỗi ô mang giá trị là độ cao của ô đó (0 <= độ cao <= 110). Bác John và bò Bessie đang ở ô trên trái (dòng 1, cột 1) và muốn đi đến cabin (dòng N, cột N). Họ có thể đi sang phải, trái, lên trên và xuống dưới nhưng không thể đi theo đường chéo. Hãy giúp bác John và bò Bessie tìm đường đi sao cho chênh lệch giữa điểm cao nhất và thấp nhất trên đường đi là nhỏ nhất.
Dữ liệu
Dòng 1: N
Dòng 2..N+1: Mỗi dòng chứa N số nguyên, mỗi số cho biết cao độ của một ô.
Kết quả
Một số nguyên là chênh lệch cao độ nhỏ nhất.
Ví dụ
Dữ liệu
5
1 1 3 6 8
1 2 2 5 5
4 4 0 3 3
8 0 2 3 4
4 3 0 2 1
Kết quả
2
2. Hướng dẫn MTWALK spoj
Dùng chặt nhị phân.
Hàm kiểm tra ta dùng BFS. Bài toán đưa về bài toán con: với độ chênh lệch nhỏ nhất là k, ta có đường đi từ ô (1,1) tới ô (n,n) hay không.
Ôi khó nói thuật cụ thể quá! Nếu các bạn không hiểu thì có thể cmt để bình luận thêm. Mình sẽ giải đáp. Cảm ơn! 😀
3. Code tham khảo MTWALK spoj
a. Code c++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 | #include <bits/stdc++.h> using namespace std; typedef pair<int,int> II; int n,a[101][101],amax=0,amin=120,lo,hi,d[101][101], pmin,pmax; II q[10001]; const int dh[]={0,0,0,-1,1}; const int dc[]={0,-1,1,0,0}; void khoitao() { for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) d[i][j]=0; } bool ok(int i, int j) { if(i>0&&i<=n&&j>0&&j<=n&&d[i][j]==0&& a[i][j]>=pmin&&a[i][j]<=pmax)return true; return false; } bool bfs() { int l=1, r=0; if(a[1][1]>=pmin&&a[1][1]<=pmax) { d[1][1]=1; q[++r]=II(1,1); } while(l<=r) { II t=q[l++]; int u=t.first,v=t.second; for(int p=1; p<=4; p++) { int u1=u+dh[p], v1=v+dc[p]; if(ok(u1,v1)) { if(u1==n&&v1==n) return true; d[u1][v1]=1; q[++r]=II(u1,v1); } } } return false; } bool f(int k) { for(int i=amin; i<=amax-k; i++) { khoitao(); pmin=i; pmax=i+k; if(bfs()) return true; } return false; } void chat() { while(hi-lo>1) { int mid=(hi+lo)/2; if(f(mid)) hi=mid; else lo=mid; } cout<<hi; } int main() { cin>>n; for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) { cin>>a[i][j]; amax=max(amax,a[i][j]); amin=min(amin,a[i][j]); } lo=-1; hi=amax-amin; chat(); } |
b. Code Pascal không chặt nhị phân
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 | const fi=''; nmax=100; cld:array[1..4] of shortint=(0,0,1,-1); clc:array[1..4] of shortint=(1,-1,0,0); type data=longint; var f:text; a:array[0..nmax+1,0..nmax+1] of data; DD:array[0..nmax+1,0..nmax+1] of boolean; n:data; Qx,Qy:array[0..nmax*nmax] of data; dau,cuoi:data; min,max,c,d:data; procedure docfile; var i,j:data; begin assign(f,fi); reset(f); readln(f,n); min:=high(data); max:=low(data); for i:=1 to n do for j:=1 to n do begin read(f,a[i,j]); if a[i,j]<d then d:=a[i,j]; if a[i,j]>c then c:=a[i,j]; end; close(f); for i:=0 to n+1 do begin dd[i,0]:=true; dd[i,n+1]:=true; dd[0,i]:=true; dd[n+1,i]:=true; end; end; procedure themvao(x,y:data); begin inc(cuoi); qx[cuoi]:=x; qy[cuoi]:=y; end; procedure layra(var x,y:data); begin x:=qx[dau]; y:=qy[dau]; inc(dau); end; function BFS(min,max:data):boolean; var i,j,x,y,u,v:data; begin dau:=1; cuoi:=0; if not ((a[1,1]>=min) and (a[1,1]<=max)) then exit(false); themvao(1,1); for i:=1 to n do for j:=1 to n do dd[i,j]:=false; while dau<=cuoi do begin layra(u,v); for i:=1 to 4 do begin x:=u+cld[i]; y:=v+clc[i]; if (dd[x,y]=false) and (a[x,y]>=min) and (a[x,y]<=max) then begin if (x=n) and (y=n) then exit(true); themvao(x,y); dd[x,y]:=true; end; end; end; exit(false); end; function gtmin(a,b:data):data; begin if a<b then exit(a); exit(b); end; procedure xuli; var i,j,res,dau,cuoi,mid,g,min,max,dd,cc:data; begin res:=high(data); if a[1,1]<a[n,n] then g:=a[1,1] else g:=a[n,n]; for min:=d to g do begin dd:=a[1,1]+a[n,n]-g; cc:=c; while dd<=cc do begin max:=(dd+cc) shr 1; if bfs(min,max) then begin res:=gtmin(res,max-min); cc:=max-1; end else dd:=max+1; end; end; writeln(res); end; begin docfile; xuli; end. |
Bài viết liên quan
- TNHWIFI spoj – Cafe wifi
- V8ORG spoj – Tổ chức đối lập
- LEM3 spoj – TRIP
- BCACM11D spoj PTIT – Đường nguyên tố
- C11BC2 spoj – Robin
- BCISLAND PTIT spoj – Nước biển
- VMUNCH spoj – Gặm cỏ
- bài giải MTNTRAI spoj THPTCBT – 21697. Nông Trại
- PTIT016E spoj PTIT – ACM PTIT 2016 E – Kỳ thi ACM/ICPC
- PBCSEQ SPOJ – Các đoạn nguyên