bài toán sa mạc

H

hai6f2009

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Bài 3. Sa mạc (6 điểm)
Một bãi sa mạc có dạng hình chữ nhật MxN. Mỗi ô vuông đơn vị trên sa mạc có một độ cao nào đó. Một người muốn đi từ bờ đầu này sang bờ cuối cùng bên kia (đi từ dòng 1 đến dòng thứ M). Người đó chỉ có thể đi từ ô đang đứng tới một ô mới theo hướng thẳng đứng chéo trái hoặc chéo phải. Giả thiết rằng người đó không được vượt ra hai mép trái và phải của sa mạc.
Hãy tìm đường đi sao cho người đó phải vượt qua quãng đường ngắn nhất. Mỗi lần đi từ một ô sang ô mới tiếp theo người đó phải đi hết quãng đường bằng độ chênh cao giữa hai ô đó.
Input: file SAMAC.INP gồm:
- Dòng đầu chứa 2 số M và N
- Dòng 2: chứa 2 số x, y là vị trí xuất phát (x: dòng, y: cột)
- M dòng tiếp theo, mỗi dòng chứa N số là độ cao của mỗi ô vuông đơn vị trên sa mạc.
Output: file SAMAC.OUT gồm:
- Dòng đầu chứa quãng đường nhỏ nhất đã đi qua.
- Dòng 2 chứa từng cặp (x,y) cho biết chỉ số dòng và cột của các ô vuông đơn vị đã đi qua.
Ví dụ:




SAMAC.INP
5 5
1 3
3 3 8 1 5
8 7 3 14 1
6 7 18 1 1
20 20 17 23 24
31 20 27 10 6
SAMAC.OUT
12
(1,3)(2,4) (3,3) (4,2) (5,2)
 
E

englandhuynh

Bài này tương tự như bài tam giác, dùng quay lui duyệt hết trường hợp rồi so sánh :-?
 
T

thienvamai

englandhuynh said:
Bài này tương tự như bài tam giác, dùng quay lui duyệt hết trường hợp rồi so sánh :-?
Bấm để xem đầy đủ nội dung ...

:3 back track nếu bạn có thừa thời gian để đợi nó duyệt hết các trường hợp khi m,n lớn thì đừng hỏi vì sao máy đơ :3.
hai6f2009 said:
Bài 3. Sa mạc (6 điểm)
Một bãi sa mạc có dạng hình chữ nhật MxN. Mỗi ô vuông đơn vị trên sa mạc có một độ cao nào đó. Một người muốn đi từ bờ đầu này sang bờ cuối cùng bên kia (đi từ dòng 1 đến dòng thứ M). Người đó chỉ có thể đi từ ô đang đứng tới một ô mới theo hướng thẳng đứng chéo trái hoặc chéo phải. Giả thiết rằng người đó không được vượt ra hai mép trái và phải của sa mạc.
Hãy tìm đường đi sao cho người đó phải vượt qua quãng đường ngắn nhất. Mỗi lần đi từ một ô sang ô mới tiếp theo người đó phải đi hết quãng đường bằng độ chênh cao giữa hai ô đó.
Input: file SAMAC.INP gồm:
- Dòng đầu chứa 2 số M và N
- Dòng 2: chứa 2 số x, y là vị trí xuất phát (x: dòng, y: cột)
- M dòng tiếp theo, mỗi dòng chứa N số là độ cao của mỗi ô vuông đơn vị trên sa mạc.
Output: file SAMAC.OUT gồm:
- Dòng đầu chứa quãng đường nhỏ nhất đã đi qua.
- Dòng 2 chứa từng cặp (x,y) cho biết chỉ số dòng và cột của các ô vuông đơn vị đã đi qua.
Ví dụ:




SAMAC.INP
5 5
1 3
3 3 8 1 5
8 7 3 14 1
6 7 18 1 1
20 20 17 23 24
31 20 27 10 6
SAMAC.OUT
12
(1,3)(2,4) (3,3) (4,2) (5,2)
Bấm để xem đầy đủ nội dung ...

gọi f(x,y) là độ dài đường đi ngắn nhất đến ô x,y;
a(x,y) là độ cao ô x,y;
đặt tất cả f(x,y) = giá trị to to vào, khoảng 1tỷ cho chắc;
ô (x1,y1) là xuất phát, đặt f(x1,y1)=0;
dùng công thức này:
f(i,j)=min(f(i-1,j-1)+|a(i,j)-a(i-1,j-1)|,f(i-1,j)+|a(i,j)-a(i-1,j)|,f(i-1,j+1)+|a(i,j)-a(i-1,j+1)|)
 
E

englandhuynh

@thienvamai: Bài này chỉ có cách giải đó là đúng mọi trường hợp, cách giải của bạn chỉ cho kết quả đúng ở một số trường hợp thôi, cách giải của bạn là lựa chọn trong 3 đường phần tử có giá trị nhỏ nhất, nhưng nếu trường hợp
1 1 1 1
0 25 15 10
0 0 100 15
0 0 15 89
1000000 0 12 29
Thì mình đảm bảo thuật toán của bạn sẽ không đúng đặc biệt là trường hợp kích thước ma trận lớn, số lớn nhất (lớn hơn tổng của mấy số còn lại) nằm ở góc và xung quang nó là số cực nhỏ.
 
T

thienvamai

englandhuynh said:
@thienvamai: Bài này chỉ có cách giải đó là đúng mọi trường hợp, cách giải của bạn chỉ cho kết quả đúng ở một số trường hợp thôi, cách giải của bạn là lựa chọn trong 3 đường phần tử có giá trị nhỏ nhất, nhưng nếu trường hợp
1 1 1 1
0 25 15 10
0 0 100 15
0 0 15 89
1000000 0 12 29
Thì mình đảm bảo thuật toán của bạn sẽ không đúng đặc biệt là trường hợp kích thước ma trận lớn, số lớn nhất (lớn hơn tổng của mấy số còn lại) nằm ở góc và xung quang nó là số cực nhỏ.
Bấm để xem đầy đủ nội dung ...

khi mình duyệt dòng cuối tìm min f(m,i)[TEX] \forall i\leq n[/TEX]
thì mình chắc chắn là không sai được
dạng này chỉ là biến thế của dạng đường đi có tổng lớn nhất mà thôi :> :>
 
M

mikelhpdatke

englandhuynh said:
@thienvamai: Bài này chỉ có cách giải đó là đúng mọi trường hợp, cách giải của bạn chỉ cho kết quả đúng ở một số trường hợp thôi, cách giải của bạn là lựa chọn trong 3 đường phần tử có giá trị nhỏ nhất, nhưng nếu trường hợp
1 1 1 1
0 25 15 10
0 0 100 15
0 0 15 89
1000000 0 12 29
Thì mình đảm bảo thuật toán của bạn sẽ không đúng đặc biệt là trường hợp kích thước ma trận lớn, số lớn nhất (lớn hơn tổng của mấy số còn lại) nằm ở góc và xung quang nó là số cực nhỏ.
Bấm để xem đầy đủ nội dung ...
Thuật toán không đúng sao? Chú lấy rõ test inp + out vd xem. :|

@thienvamai:
Thêm phần điền cơ sở QHĐ vào cho chắc ;))

P/s: Thuật chắc chắn đúng ;))
 
T

thienvamai

Đây là biến thể của 1 bài QHĐ cơ bản thôi mà :3
cơ sở tất cả f(i,j) = 1 số lớn, nhưng ko được là số lớn quá, nếu không khi cộng thêm khoảng cách bị lỗi, riêng f(x,y) =0 (x,y) là điểm bắt đầu
sau đó tìm các dòng tiếp theo
dòng cuối tìm fmin theo các f của dòng đấy
 
H

hai6f2009

exitcode=201

ừ thì mình cũng optimize giống y đúc vậy nhưng quên mất cách trace rồi :(!
đành chém code đại như vầy :D! mà nó bị exitcode=201. có ai giúp mình với :)!
Mã: 
program samac;
const   fi='samac.inp';
        fo='samac.out';
var     f:text;
        m,n,u,v:integer;
        a,b:array[1..10000,1..10000] of integer;
        c,s,p:array[1..10000] of integer;
        min:integer;
procedure enter;
var i,j:integer;
begin
 assign(f,fi);reset(f);
 readln(f,m,n);
 readln(f,u,v);
 for i:=1 to m do
  for j:=1 to n do
   begin
    read(f,a[i,j]);
    if j=n then readln(f);
   end;
 close(f);
end;

function gtnn(x,y:integer):integer;
begin
 if x<y then exit(x) else exit(y);
end;

function gtnn2(x,y,z:integer):integer;
begin
 if (x<y) and (x<z) then exit(x)
 else if (y<x) and (y<z) then exit(y)
 else exit(z);
end;

procedure optimize;
var i,j:integer;
begin
 for j:=1 to n do b[1,j]:=0;
 for i:=1 to m do
  b[i,1]:=gtnn((b[i-1,1]+abs(a[i,1]-a[i-1,1])), (b[i-1,2]+abs(a[i,1]-a[i-1,2])));
 for i:=2 to m do
  for j:=2 to n-1 do
   b[i,j]:=gtnn2((b[i-1,j-1]+abs(a[i,j]-a[i-1,j-1])),(b[i-1,j]+abs(a[i,j]-a[i-1,j])),(b[i-1,j+1]+abs(a[i,j]-a[i-1,j+1])));
 for i:=2 to m do
  b[i,n]:=gtnn((b[i-1,n]+abs(a[i,n]-a[i-1,n])),(b[i-1,j]+abs(a[i,n]-a[i-1,n-1])));
end;

procedure trace;
var i,j,k,cs:integer;
begin
 min:=b[m,1];
 for j:=1 to n do
  if min>b[m,j] then
   begin
    min:=b[m,j];
    cs:=j;
   end;
 i:=n;j:=cs; c[i]:=j;
 while i>1 do
  begin
   k:=b[i,j];
   dec(i);
   s[i]:=i;
   c[i]:=k;
   j:=k;
   p[i]:=k;
  end;
end;

procedure printresult;
var i,j:integer;
begin
 assign(f,fo);rewrite(f);
 writeln(f,min);
 for i:=1 to n do write (f,'(',s[i] ,',',p[i],')');
 writeln(f,'(',u,',',v,')');
 close(f);
end;

BEGIN
 enter;
 optimize;
 trace;
 printresult;
END.
 
Last edited by a moderator:
T

thienvamai

201: Range check error
If you compiled your program with range checking on, then you can get this error in the following cases:
1 . An array was accessed with an index outside its declared range.
2 . Trying to assign a value to a variable outside its range (for instance an enumerated type).
 
H

hai6f2009

nhưng chỗ trace của mình sai chỗ nào không bạn? mình chỗ nhớ chỗ quên :D
 
M

mikelhpdatke

Tổng hợp các lỗi trong Free Pascal khi biên dịch



@thienvamai:
Truy viết thì dựa vào Optimize mà chiến thôi ;))
Đầu tiên tìm ô ở hàng cuối cùng là nghiệm của bài toán.
Giả sử là A(n,j)
Ô tiếp theo cần in sẽ là 1 trong 3 ô A(n-1,j); A(n-1,j-1); A(n-1; j+1) sao cho 1 trong 3 ô có giá trị = F[n,j]- ABS(A[n,j]-A[x1,x2]) { x1, x2 là tọa độ tương ứng nhé}
 
1

11thanhkhoeo

chết nhầm

Chênh lẹch ngắn nhất

không phải đường đi ngắn nhất
 
E

englandhuynh

ak thuật này đúng rồi tại mình đọc lướt qua công thức tưởng là tham lam.
 
H

hai6f2009

nhìn lại mình mới thấy hình như cái cơ sở qhd của mình chưa đúng thì phải =.= ! có ai chỉ lại cho mình được không?
 
N

Nickersociker

Học sinh mới
Thành viên
3 Tháng ba 2019
7
0
1
19
Bình Định
Trường THPT Nguyễn Trân
Nếu đề bài là như thế này và có phần truy vết đường đi thì code của mình sẽ là:
Bài 5: Bài toán ″Sa mạc ″. SAMAC.PAS
Một bãi sa mạc có dạng hình chữ nhật MxN. Mỗi ô vuông đơn vị trên sa mạc có một độ
cao nào đó. Một người muốn đi từ bờ đầu này sang bờ cuối cùng bên kia. Người đó chỉ có
thể đi từ ô đang đứng tới một ô mới theo hướng thẳng đứng chéo trái hoặc chéo phải. Giả
thiết rằng người đó không được vượt ra hai mép trái và phải của sa mạc.
Hãy tìm đường đi sao cho người đó phải vượt qua quãng đường ngắn nhất. Mỗi lần đi từ
một ô sang ô mới tiếp theo người đó phải đi hết quãng đường bằng độ chênh cao giữa hai ô
đó.
Dữ liệu vào: Từ tệp SAMAC.INP với cấu trúc sau
- Dòng 1 gồm 2 giá trị M, N được viết cách nhau bởi dấu cách
- M dòng tiếp theo mỗi dòng chứa N giá trị viết cách nhau bởi dấu cách.
Dữ liệu ra: Ghi vào tệp SAMAC.OUT, một số nguyên duy nhất thể hiện giá trị nhỏ
nhất của đường đi để người đó vượt qua được sa mạc (đến được hàng thứ M).
Ví dụ:
SAMAC.INP
5 5
3 3 8 1 5
8 7 3 14 1
6 7 18 1 1
20 20 17 23 24
31 20 27 10 6
SAMAC.OUT
12
(1,3) (2,4) (3,3) (4,2) (5,2)
**CODE**:
type matrix=array[0..255,0..255] of longword;
var a,f:matrix;
m,n,i:byte;
j:longword;
function min(a,b,c:longword):longword;
begin
if (b<a) and (b<c) then exit(b);
if (a<b) and (a<c) then exit(a);
if (c<a) and (c<b) then exit(c);
exit(a);
end;
function sum(i,j,ii,jj:byte):longword;
begin
sum:=f[ii,jj]+abs(a[i,j]-a[ii,jj]);
end;
procedure born;
begin
fillchar(f,sizeof(f),0);
for i:=1 to m do a[i,0]:=a[i,2];
for i:=1 to m do a[i,n+1]:=a[i,n-1];
for i:=2 to m do
for j:=1 to n do
begin
f[i,j]:=min(sum(i,j,i-1,j-1),sum(i,j,i-1,j+1),sum(i,j,i-1,j));
if j=2 then f[i,0]:=f[i,2];
if j=n-1 then f[i,n+1]:=f[i,j];
end;
end;
procedure trace(i,j:byte);
begin
if (sum(i,j,i-1,j-1)=f[i,j]) and (j-1>0) then trace(i-1,j-1)
else if (sum(i,j,i-1,j+1)=f[i,j]) and (j+1<=n) then trace(i-1,j+1)
else if (sum(i,j,i-1,j)=f[i,j]) and (i-1>=1) then trace(i-1,j);
write('(',i,',',j,') ');
end;
BEGIN
assign(input,'SAMAC.INP'); reset(input);
assign(output,'SAMAC.OUT'); rewrite(output);
while not eof(input) do
begin
readln(m,n);
for i:=1 to m do
begin
for j:=1 to n do read(a[i,j]); readln;
end;
born;
j:=f[m,1];
for i:=1 to n do if f[m,i]<j then j:=f[m,i];
writeln(j);
for i:=1 to n do
if f[m,i]=j then
begin
trace(m,i); writeln;
end;
end;
END.
// Nếu có gì cần code lại nhờ mấy bạn comment nha :D:D:D
:Tuzki17:Tuzki17:Tuzki17:Tuzki17:Tuzki17:Tuzki17:Tuzki17
 
hienithue1418

hienithue1418

Học sinh mới
Thành viên
28 Tháng mười một 2020
2
0
1
37
Thừa Thiên Huế
phan dang luu
hàng cuối cùng min chưa chắc là đáp án vì có thể không phải kết quả của ô xuất phát

Nickersociker said:
Nếu đề bài là như thế này và có phần truy vết đường đi thì code của mình sẽ là:
Bài 5: Bài toán ″Sa mạc ″. SAMAC.PAS
Một bãi sa mạc có dạng hình chữ nhật MxN. Mỗi ô vuông đơn vị trên sa mạc có một độ
cao nào đó. Một người muốn đi từ bờ đầu này sang bờ cuối cùng bên kia. Người đó chỉ có
thể đi từ ô đang đứng tới một ô mới theo hướng thẳng đứng chéo trái hoặc chéo phải. Giả
thiết rằng người đó không được vượt ra hai mép trái và phải của sa mạc.
Hãy tìm đường đi sao cho người đó phải vượt qua quãng đường ngắn nhất. Mỗi lần đi từ
một ô sang ô mới tiếp theo người đó phải đi hết quãng đường bằng độ chênh cao giữa hai ô
đó.
Dữ liệu vào: Từ tệp SAMAC.INP với cấu trúc sau
- Dòng 1 gồm 2 giá trị M, N được viết cách nhau bởi dấu cách
- M dòng tiếp theo mỗi dòng chứa N giá trị viết cách nhau bởi dấu cách.
Dữ liệu ra: Ghi vào tệp SAMAC.OUT, một số nguyên duy nhất thể hiện giá trị nhỏ
nhất của đường đi để người đó vượt qua được sa mạc (đến được hàng thứ M).
Ví dụ:
SAMAC.INP
5 5
3 3 8 1 5
8 7 3 14 1
6 7 18 1 1
20 20 17 23 24
31 20 27 10 6
SAMAC.OUT
12
(1,3) (2,4) (3,3) (4,2) (5,2)
**CODE**:
type matrix=array[0..255,0..255] of longword;
var a,f:matrix;
m,n,i:byte;
j:longword;
function min(a,b,c:longword):longword;
begin
if (b<a) and (b<c) then exit(b);
if (a<b) and (a<c) then exit(a);
if (c<a) and (c<b) then exit(c);
exit(a);
end;
function sum(i,j,ii,jj:byte):longword;
begin
sum:=f[ii,jj]+abs(a[i,j]-a[ii,jj]);
end;
procedure born;
begin
fillchar(f,sizeof(f),0);
for i:=1 to m do a[i,0]:=a[i,2];
for i:=1 to m do a[i,n+1]:=a[i,n-1];
for i:=2 to m do
for j:=1 to n do
begin
f[i,j]:=min(sum(i,j,i-1,j-1),sum(i,j,i-1,j+1),sum(i,j,i-1,j));
if j=2 then f[i,0]:=f[i,2];
if j=n-1 then f[i,n+1]:=f[i,j];
end;
end;
procedure trace(i,j:byte);
begin
if (sum(i,j,i-1,j-1)=f[i,j]) and (j-1>0) then trace(i-1,j-1)
else if (sum(i,j,i-1,j+1)=f[i,j]) and (j+1<=n) then trace(i-1,j+1)
else if (sum(i,j,i-1,j)=f[i,j]) and (i-1>=1) then trace(i-1,j);
write('(',i,',',j,') ');
end;
BEGIN
assign(input,'SAMAC.INP'); reset(input);
assign(output,'SAMAC.OUT'); rewrite(output);
while not eof(input) do
begin
readln(m,n);
for i:=1 to m do
begin
for j:=1 to n do read(a[i,j]); readln;
end;
born;
j:=f[m,1];
for i:=1 to n do if f[m,i]<j then j:=f[m,i];
writeln(j);
for i:=1 to n do
if f[m,i]=j then
begin
trace(m,i); writeln;
end;
end;
END.
// Nếu có gì cần code lại nhờ mấy bạn comment nha :D:D:D
:Tuzki17:Tuzki17:Tuzki17:Tuzki17:Tuzki17:Tuzki17:Tuzki17
Bấm để xem đầy đủ nội dung ...
bài này có điểm xuất phát chứ không phải tính cả bảng nhé!
 
Last edited by a moderator:
khanhduy2311

khanhduy2311

Học sinh
Thành viên
23 Tháng tám 2020
26
21
21
Bình Định
Trường Trung học cơ sở An Hòa
#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
#define ll long long
#define TASK "samac"
using namespace std;

int a[200][200];
int n,m;

int main(){
#ifndef ONLINE_JUDGE
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
#endif
cin>>m>>n;
//Doc du lieu vao cho mang A
fo(j,1,m)
fo(i,1,n) {cin >> a[j];}

int b[200][200];
int t[200][200];
b[1][1]=a[1][1];

fo(i,2,n) {b[1]=b[1][i-1]+a[1][i-1]; t[1]=2;}

fo(i,2,m) {b[1]=b[i-1][1]+a[1]; t[1]=1;}

fo(j,2,m)
fo(i,2,n)
if (b[j-1]>= b[j][i-1]) {b[j]=b[j-1]+ a[j]; t[j]=1;}
else {b[j]=b[j][i-1]+ a[j];t[j]=2;}

//Thong bao tong nang luong thu duoc
cout<<b[m][n]<<endl;
int c[n+m][2];
int k=1;
int j=m, i=n;
while ((j>=1)&& (i>=1))
{
c[k][0]=j; c[k][1]=i;
if (t[j]==1) j--;
else i--;
k++;
}

fd(i,k-1,1) cout<<c[0]<<" "<<c[1]<<endl;

}
 
  • Like
Reactions: Elishuchi
You must log in or register to reply here.
Top Bottom