Nguồn đề bài http://vn.spoj.com/problems/MTWALK/
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++
#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
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.
