MTWALK spoj - Mountain Walking

Nguồn đề bài http://vn.spoj.com/problems/MTWALK/

Nội dung bài viết

1. Đề bài MTWALK spoj
2. Hướng dẫn MTWALK spoj
3. Code tham khảo MTWALK spoj
- a. Code c++
- b. Code Pascal không chặt nhị phân

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();
}

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

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;

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;

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;

writeln(res);

end;

begin

docfile;

xuli;

end.

MTWALK spoj – Mountain Walking

1. Đề bài MTWALK spoj

2. Hướng dẫn MTWALK spoj

3. Code tham khảo MTWALK spoj

a. Code c++

b. Code Pascal không chặt nhị phân

Bài viết liên quan

Trả lời Hủy