View Full Version : Pascal : 1 bài toán Đồ thị hay
elnino_020993
18-07-2009, 08:47
003. CARGO
Bản đồ một kho hàng hình chữ nhật kích thước mxn được chia thành các ô vuông đơn vị (m hàng, n cột: các hàng đánh số từ trên xuống dưới, các cột đánh số từ trái qua phải). Trên các ô của bản đồ có một số ký hiệu:
Các ký hiệu # đánh dấu các ô đã có một kiện hàng xếp sẵn,
Một ký hiệu *: Đánh dấu ô đang có một xe đẩy
Một ký hiệu $: Đánh dấu ô chứa kiện hàng cần xếp
Một ký hiệu @: Đánh dấu vị trí ô mà cần phải xếp kiện hàng B vào ô đó
Các ký hiệu dấu chấm ".": Cho biết ô đó trống
Cần phải dùng xe đẩy ở * để đẩy kiện hàng ở $ đến vị trí @ sao cho trong quá trình di chuyển cũng như đẩy hàng, không chạm vào những kiện hàng đã được xếp sẵn. (Xe đẩy có thể di chuyển sang một trong 4 ô chung cạnh với ô đang đứng). Nếu có nhiều phương án thì chỉ ra một phương án sao cho xe đẩy phải di chuyển qua ít bước nhất.
Dữ liệu: Vào từ file van bản CARGO.INP
Dòng 1: Ghi hai số nguyên dương m, n cách nhau một dấu cách (m, n 80)
m dòng tiếp theo, dòng thứ i ghi đủ n ký hiệu trên hàng thứ i của bản đồ theo đúng thứ tự từ trái qua phải. Các ký hiệu được ghi liền nhau
Kết quả: Ghi ra file van bản CARGO.OUT
Ghi số bước di chuyển xe đẩy để thực hiện mục đích yêu cầu, nếu không có phương án khả thi thì ghi số -1
Ví dụ:
CARGO.INP
8 8
########
#.....@.
.....###
........
#.#####*
.$......
........
........
CARGO.OUT
23
CARGO.INP
5 9
@........
.##.###.#
......#..
.##$###.#
.*.......
CARGO.OUT
22
đây là 1 bài toán đồ thị trong sách của thầy Lê Minh Hoàng, mình đã lược bỏ bớt, giữ lại ý chính thôi ( ko có phần truy vết )
mong các bạn cùng tham gia
có lẽ loang từ xe đẩy đến kiện hàng , rồi loang từ kiện hàng đến @ , chừa mấy # ra , không dược loang vào đó
mấy bài tìm số bước nhỏ nhất này e nghĩ BFS là chuẩn
ko biết ý a ra sao
elnino_020993
18-07-2009, 09:06
là BFS,
ai có code share nhe, 1 phần công việc nho nhỏ thôi cũng được
phân tích chỉ làm cho mình có thuật toán thôi, ko thể xem là đã làm bài hoàn thiện được
[=========> Bổ sung bài viết <=========]
mà khi kiện hàng rẽ hướng thì cái xe đẩy cũng phải đổi hướng trước đó, thế mới đẩy được
cụ thể là đẩy hàng theo kiểu kiện đi trước , xe đi sau đẩy hay là chất kiện lên xe rồi đẩy đi ?
elnino_020993
18-07-2009, 09:18
là kiện hàng đi trước, xe đẩy kiện hàng
chứ nếu là bỏ kiện hàng lên xe thì bài này còn gì để nói, quá sáng tỏ rồi mà
ngtrhieu0011
18-07-2009, 12:22
loang BFS, nhưng xét các trường hợp:
Quẹo trái/phải: 3 ô ... fải trống
Quay lại 180độ: 5 ô ... fải trống
elnino_020993
19-07-2009, 11:55
các bạn xem ra ko thích đồ thị lắm thì phải,
tui lại dở QHĐ, hix
@elnino : a hieu nói đúng rồi mà , a cứ loang , rồi sử dụng mảng đề lưu hướng đi như lần trước , đổi hướng thì check 3 ô có trống ko ...
(nói như vậy nhưng e vẫn chưa nghĩ đến chuyện code sẽ có khó khăn gì ...)
elnino_020993
20-07-2009, 16:51
bạn nào tạo code cho mình xin nhe
thanks trước cái :D
Toàn pro trong topic này nhỉ. Đồ thị mình mới đọc đến phần cây khung. Đau đầu kinh khủng. Ko biết khoảng 1 tuần có đủ nhồi nhét hết 7 phần còn lại không
Toàn pro trong topic này nhỉ. Đồ thị mình mới đọc đến phần cây khung. Đau đầu kinh khủng. Ko biết khoảng 1 tuần có đủ nhồi nhét hết 7 phần còn lại không
kinh thế , mình mới xong prim à , rồi dừng lại , ko đọc nữa vì đề thi Qg THCS sẽ không ác đến nỗi ra luồng cực đại hay mấy ông gì gì đó , đâu , cứ nắm thật vững mấy ông từ bắt đầu đến cậy khung là được rồi , (đau đầu nhất là ông tarjan và dijkstra , prim +heap )
[=========> Bổ sung bài viết <=========]
@quang : bây giờ bạn tự lập , cài heap với dijkstra thử xem ,không vững là chết liền , học có xa đến mấy cài ko dc , thiéu lên thiếu xuống là tèo
elnino_020993
21-07-2009, 09:06
tụi em thế là giỏi lắm đấy
biết không, anh bằng tuổi em hiện nay thì anh còn chưa biết đến Pascal đấy
[=========> Bổ sung bài viết <=========]
anh mới học pascal được 2 năm àh (năm lớp 9 vừa học vừa chơi, ko vào đầu được cái gì, biết mỗi vòng for ra sao, chấm hết)
Chuẩn, tarjan ngồi đọc >1 buổi mới hiểu.
Đang đọc dijkstra.
Thấy tìm đường hay thật, gặp bài tương tự Ng du lịch thì đỡ phải đệ quy
ngtrhieu0011
21-07-2009, 17:28
vậy em biết thuật toán Dijkstra có tư tưởng của dạng toán jì không?
qui hoạch động , cũng giống như ford bellman với floyd thôi ^^
Chính xác. Đang định trả lời.
Thể hiện rõ nhất ở Floyd.
elnino_020993
24-07-2009, 09:59
ko ai chịu giải bài này àh,
hix
thế a ko có ý tưởng gì à ? ý của a hiếu là trống 3 ô để rẽ , còn cài đặt loang thì a rành lắm mà >... e ko giỏi , nhưng sẽ suy nghĩ cài đặt sao cho tốt
elnino_020993
27-07-2009, 22:02
type ovuong=record
x,y:longint;
end;
const fi='CARGO.INP';
fo='CARGO.OUT';
tdi:array[1..4] of shortint = (-1,0,0,1);
tdj:array[1..4] of shortint = (0,1,-1,0);
var f:text;
kq,n,m,x1,x2,y1,y2,p,q:longint;
hd,luu:array[1..200] of ovuong;
dem:array[1..200] of longint;
dd:array[1..80,1..80] of longint;
procedure docfile;
var i,j:longint;
c:char;
begin
assign(f,fi);
reset(f);
readln(f,n,m);
for i:=1 to n do
begin
for j:=1 to m do
begin
read(f,c);
if c='#' then dd[i,j]:=2
else if c='@' then
begin
x2:=i;y2:=j;
end
else if c='*' then
begin
p:=i;q:=j;
end
else if c='$' then
begin
x1:=i;y1:=j;
end;
end;
readln(f);
end;
close(f);
end;
procedure tim(x1,y1,x2,y2,x3,y3:longint;var l:longint);
var u,v,i,j,k,d,c:longint;
hd:array [1..200] of ovuong;
dem,dda:array[1..80,1..80] of longint;
begin
l:=-1;
if (x1=x2) and (y1=y2) then
begin
l:=0;
exit;
end;
if (x2<1) or (x2>n) or (y2<1) or (y2>m) then exit;
d:=1;c:=1;
hd[d].x:=x1;hd[d].y:=y1;
dda:=dd;
dda[x1,y1]:=2;
dda[x3,y3]:=2;
dem[x1,y1]:=0;
repeat
u:=hd[d].x;v:=hd[d].y;
for k:=1 to 4 do
begin
i:=u+tdi[k];j:=v+tdj[k];
if (i>=1) and (i<=n) and (j>=1) and (j<=m) and (dda[i,j]<2) then
begin
inc(c);
hd[c].x:=i;hd[c].y:=j;
dda[i,j]:=2;
dem[i,j]:=dem[u,v]+1;
if (i=x2) and (j=y2) then
begin
l:=dem[x2,y2];
exit;
end;
end;
end;
inc(d);
until d>c;
end;
procedure xuly;
var d,c,u,v,i,j,k,l:longint;
begin
d:=1;c:=1;
hd[d].x:=x1;hd[d].y:=y1;
luu[d].x:=p;luu[d].y:=q;
dd[x1,y1]:=1;
kq:=maxlongint;
repeat
u:=hd[d].x;v:=hd[d].y;
for k:=1 to 4 do
begin
i:=u+tdi[k];j:=v+tdj[k];
if (i>=1) and (i<=n) and (j>=1) and (j<=m) then
if (dd[i,j]<1) then
begin
tim(luu[d].x,luu[d].y,u+tdi[5-k],v+tdj[5-k],u,v,l);
if l>=0 then
begin
inc(c);
hd[c].x:=i;hd[c].y:=j;
luu[c].x:=u;luu[c].y:=v;
dd[i,j]:=1;
dem[c]:=dem[d]+l+1;
if (i=x2) and (j=y2) then
if kq>dem[c] then
begin
kq:=dem[c];
dd[x2,y2]:=0;
end;
end;
end;
end;
inc(d);
until d>c;
if kq=maxlongint then kq:=-1;
end;
procedure ghifile;
begin
assign(f,fo);
rewrite(f);
writeln(f,kq);
close(f);
end;
begin
docfile;
xuly;
ghifile;
end.
ai có cải tiến hay cho xin code
ax, e tệ nhất là đọc code của người khác ^^. có thể nói là trước giờ e chưa đọc code nào dài hơn 50 line. thầy là tránh, a nói thuật toán đi
elnino_020993
28-07-2009, 07:35
tư tưởng cực đơn giản, chỉ là muốn trải nghiệm xem cài đặt nó có những vấn đề nào phát sinh + giải quyết nó như thế nào thôi
thế này nhé, loang theo thùng hàng, với mỗi bước, loang cho xe hàng, vd
#1#
2$3
#4#
tất nhiên, muốn xe hàng đi hướng i thì loang xe đẩy vào hướng (5-i)
khi loang đến đích thì kiểm tra con đường nào ngắn nhất
xong rồi đó, còn phần truy vết thì ai có cao kiến gì ko
Powered by vBulletin® Version 4.2.0 Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.