Tim đường đi ngắn nhất

[[T][a][r][a]]

Mê cung HCN kích thước m x gồm các ô vuông đơn vi (m,n<=1000).Trên mỗi ô vuông ghi 1 trong 3 kí tự:
_ O: Nếu ô dó an toàn
_ X: Nếu ô đó có cạm bẫy
_ E: Nếu là ô có 1 nhà thám hiểm đang đứng
Duy nhất chỉ có 1 ô ghi chữ E. Nhà thám hiểm có thể từ 1 ô đi sang một trong số các ô chung cạnh với ô đang đứng ( tức là có 4 ô có thể đi đến theo hàng ngang và dọc). Môt cách đi thoát khỏi mê cung là 1 hành trình đi qua các ô an toàn ra 1 ô BIÊN. Hãy chỉ cho nhà thám hiểm thoát ra khỏi mê cung đi qua ít ô nhất
File vào:
dòng đâu ghi n,m
n dòng tiếp theo, ghi m kí tự là trạng thái của các ô trong mê cung
File ra:
Ghi hành trình, ví dụ : (i,j)->(q,w)->....

[HGMinh95]

Bạn có thể dùng BFS.
Đầu tiên từ ô E, đánh dấu tất cả các ô có thể đi đến từ ô này (không phải là ô cạm bẫy) là 1; sau đó với các ô 1, bạn lại đánh dấu những ô có thể đi đến được từ những ô này là 2,... tiếp tục như vậy cho đến khi tìm ra được 1 ô ở biên. Muốn tìm ra được hành trình thì bạn chỉ cần tìm ngược lại từ ô biên đến ô E.
Ví dụ ô biên được đánh dấu là 5, tìm 1 ô xung quanh ô biên ô đánh dấu là 4,.. tiếp tục cho đến khi tìm thấy ô E

[[T][a][r][a]]

Thanks bạn rất nhiều, cách của bạn quả thật rất hay. Sáng nay mới ở trên trường, cô mình giảng bài này dài lắm, nào là mảng 1 2 chiều, biến kiểu bảng ghi nhức hết cả đầu. Để mình về làm chạy thử cách bạn xem sao ^^

[=========> Bổ sung bài viết <=========]

À mà bạn ơi, cách bạn hình như không dùng BFS cũng được mà ??

[HGMinh95]

[a][r][a];2650762']À mà bạn ơi, cách bạn hình như không dùng BFS cũng được mà ??
Phương pháp của mình là loang nhưng thực chất cũng là BFS mà

[[T][a][r][a]]

Bạn ơi hình như cách của bạn không ổn rồi, mình đã thử khi đến lần đánh dấu số 3 thì nó sẽ ghi đè lên các ô đã đánh dấu trước đó số 4-> làm đường đi trước đó bị mất đi. Bài này khó là ở chỗ tổ chức dữ liệu ra sao thôi bạn à, nếu bạn làm rồi có thể cho mình đoạn code được không ? :)

[HGMinh95]

Tạo mảng A[1..m,1..n] 2 chiều lưu trữ mê cung mxn
- Nếu A[i,j] an toàn và chưa đánh dấu thì A[i,j]=0
- Nếu A[i,j] là bạm bẫy thì A[i,j]=-1;
- Nếu A[i,j] là ô E thì A[i,j]=-2
Khi duyệt, bạn chỉ đánh dấu những ô A[i,j]=0 thôi

[[T][a][r][a]]

Bạn không hiểu ý mình rồi, thế này nhé, giả sử có 1 mê cung không có ô cạm bẫy nào, thì lần đánh dâu trước sẽ có khả năng đánh dấu lấp đi ô đã đánh trước đó

[HGMinh95]

Nếu bạn làm như mình thì sẽ không đánh dấu lại những ô đã đánh dấu

[[T][a][r][a]]

Bạn có thể viết bài này rồi cho mình code được không, cái này khó viết quá, khó hiểu nữa :P

[zmt264]

[a][r][a];2650024']Mê cung HCN kích thước m x gồm các ô vuông đơn vi (m,n<=1000).Trên mỗi ô vuông ghi 1 trong 3 kí tự:
_ O: Nếu ô dó an toàn
_ X: Nếu ô đó có cạm bẫy
_ E: Nếu là ô có 1 nhà thám hiểm đang đứng
Duy nhất chỉ có 1 ô ghi chữ E. Nhà thám hiểm có thể từ 1 ô đi sang một trong số các ô chung cạnh với ô đang đứng ( tức là có 4 ô có thể đi đến theo hàng ngang và dọc). Môt cách đi thoát khỏi mê cung là 1 hành trình đi qua các ô an toàn ra 1 ô BIÊN. Hãy chỉ cho nhà thám hiểm thoát ra khỏi mê cung đi qua ít ô nhất
File vào:
dòng đâu ghi n,m
n dòng tiếp theo, ghi m kí tự là trạng thái của các ô trong mê cung
File ra:
Ghi hành trình, ví dụ : (i,j)->(q,w)->....

Bạn học trường nào mà thày cô ra bài tập khó kinh dị thế :(

[HGMinh95]

Đây là đoạn code, input được nhập từ file thamhiem.inp
Để đơn giản mình chỉ ghi ra mê cung sau khi đánh dấu và ô biên gần nhất ra được



uses crt;
type L = record
x,y:integer;
end;
var a:array[0..100,0..100] of integer;
m,n,x,y:byte;
Res:L;

procedure Init;
var i:integer;
begin
clrscr;
for i:=0 to n+1 do
begin
a[i,0]:=-1;
a[i,n+1]:=-1;
end;
for i:=0 to m+1 do
begin
a[0,i]:=-1;
a[n+1,i]:=-1;
end;
end;
procedure Enter;
var f:text;
i,j:byte;
c:char;
begin
assign(f,'thamhiem.inp');
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='O' then a[i,j]:=0;
if c='X' then a[i,j]:=-1;
if c='E' then
begin
a[i,j]:=-2;
x:=i; y:=j;
end;
end;
readln(f);
end;
close(f);
end;
procedure BFS;
var Queue: array[1..1000] of L;
Front, Rear: integer;
u,v:L;
i,j:integer;
begin
Front:=1; Rear:=1;
Queue[1].x:=x; Queue[1].y:=y;
repeat
u:=Queue[Front]; inc(Front);
if (u.x=1) or (u.x=n) or (u.y=m) or (u.y=1) then
begin
Res.x:=u.x;
Res.y:=u.y;
break;
end;
for i:=-1 to 1 do
for j:=-1 to 1 do
if (abs(i)<>abs(j)) and (a[u.x+i,u.y+j]=0) then
begin
v.x:=u.x+i; v.y:=u.y+j;
inc(Rear); Queue[Rear]:=v;
if a[u.x,u.y]=-2 then a[v.x,v.y]:=1
else a[v.x,v.y]:=a[u.x,u.y]+1;
end;
until Front > Rear
end;

procedure PrintResult;
var i,j:integer;
begin
for i:=1 to n do
begin
for j:=1 to m do write(a[i,j]:3);
writeln;
end;
write(Res.x,' ',Res.y);
end;

begin
Enter;
Init;
BFS;
PrintResult;
readln
end.

[[T][a][r][a]]

Bạn học trường nào mà thày cô ra bài tập khó kinh dị thế :(
Mình học chuyên quốc học huế bạn à ^^

[=========> Bổ sung bài viết <=========]


Đây là đoạn code, input được nhập từ file thamhiem.inp
Để đơn giản mình chỉ ghi ra mê cung sau khi đánh dấu và ô biên gần nhất ra được



uses crt;
type L = record
x,y:integer;
end;
var a:array[0..100,0..100] of integer;
m,n,x,y:byte;
Res:L;

procedure Init;
var i:integer;
begin
clrscr;
for i:=0 to n+1 do
begin
a[i,0]:=-1;
a[i,n+1]:=-1;
end;
for i:=0 to m+1 do
begin
a[0,i]:=-1;
a[n+1,i]:=-1;
end;
end;
procedure Enter;
var f:text;
i,j:byte;
c:char;
begin
assign(f,'thamhiem.inp');
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='O' then a[i,j]:=0;
if c='X' then a[i,j]:=-1;
if c='E' then
begin
a[i,j]:=-2;
x:=i; y:=j;
end;
end;
readln(f);
end;
close(f);
end;
procedure BFS;
var Queue: array[1..1000] of L;
Front, Rear: integer;
u,v:L;
i,j:integer;
begin
Front:=1; Rear:=1;
Queue[1].x:=x; Queue[1].y:=y;
repeat
u:=Queue[Front]; inc(Front);
if (u.x=1) or (u.x=n) or (u.y=m) or (u.y=1) then
begin
Res.x:=u.x;
Res.y:=u.y;
break;
end;
for i:=-1 to 1 do
for j:=-1 to 1 do
if (abs(i)<>abs(j)) and (a[u.x+i,u.y+j]=0) then
begin
v.x:=u.x+i; v.y:=u.y+j;
inc(Rear); Queue[Rear]:=v;
if a[u.x,u.y]=-2 then a[v.x,v.y]:=1
else a[v.x,v.y]:=a[u.x,u.y]+1;
end;
until Front > Rear
end;

procedure PrintResult;
var i,j:integer;
begin
for i:=1 to n do
begin
for j:=1 to m do write(a[i,j]:3);
writeln;
end;
write(Res.x,' ',Res.y);
end;

begin
Enter;
Init;
BFS;
PrintResult;
readln
end.
Cảm ơn bạn, bạn thực sự rất giỏi ^^. Kiểu này mình sẽ nhờ bạn nhìu đây, thanks bạn lần nữa nha ^^:P

[=========> Bổ sung bài viết <=========]

À cho mình hỏi thêm bạn học trường nào thế HGMinh95 ^^ ??

[HGMinh95]

[a][r][a];2654380']À cho mình hỏi thêm bạn học trường nào thế HGMinh95 ^^ ??
Mình học trường Cổ Loa

[03YQcicely]

1. amateur interracial tube fcc amateur radio license database

+ bbw amateur videos (http://www.steklosouz.ru/forum_/profile.php?mode=viewprofile&u=11494)
- amateur emo blowjob
+ free amateur video downloads (http://forum.webiznow.com/index.php?action=profile;u=15327)
- *** amateur hour
+ amateur t girls (http://www.pazaryolu25.com/forum/profile.php?mode=viewprofile&u=82801)
- free amateur fisting videos
+ your amateur *** (http://www.crazybobsplace.net/smf/index.php?action=profile;u=120056)
- amateur radio interference
+ ***e fellation amateur (http://dangerousrubber.net23.net/index.php?action=profile;u=1041)
- **** amateur videos

a. kenwood amateur, amateur boob flash, amateur swinger club
b. amateur webcam orgasm, asian amateur teens, women nude amateur
c. big tits amateur, amateur club usa, free homemade amateur vids

+ amateur nudist galleries (http://pim0110.no-ip.org/phpbb3/memberlist.php?mode=viewprofile&u=877)
- videos amateur lesbianas
+ amateur teen cleavage (http://www.darrylyao.com/forum/profile.php?mode=viewprofile&u=121198)
- amateur asian couples
+ amateur accidental nudity (http://flip-top-head.co.uk/forum/index.php?action=profile;u=13586)
- your amateur ponr
+ amateur cuckold clips (http://www.wandabcampbell.net/forum/profile.php?mode=viewprofile&u=308)
- amateur photography classes
+ free long amateur videos (http://porte-fun.lar.jp/phpbb/profile.php?mode=viewprofile&u=213877)
- husband and wife amateur ***

d. home made amateur ***, japanese *** amateur, amateur drama group
e. thesaurus amateur, amateur swallow, handjob amateur
f. amateur strippoker, awesome amateur lesbian lovemaking, amateur free *** sites

2. amateur lesbians licking pussy amateur *** wife

+ amateur lesbian vids (http://www.sienaatavola.it/forum/pop_profile.asp?mode=display&id=8252)
- free **** amateur movie
+ x video amateur (http://www.tattoosfromthesoul.com/forum/profile.php?mode=viewprofile&u=178648)
- amateur gay masturbation
+ amateur erotic photo (http://www.mokambo.es/foromokambo/profile.php?mode=viewprofile&u=219906)
- amateur allure mindy
+ amateur home vid (http://www.cruiseshipdjs.info/member.php?78678-01JKgena)
- amateur housewife ***
+ beautiful amateur nude (http://www.parismusicclub.com/forum/index.php?action=profile;u=29891)
- amateur girl cum

a. amateur lesbian ass licking, amateur clevage, chicas amateur con cam
b. you amateur, amateur tube ***, amateur homemade adult
c. amateur movies net, amateur girlfriend creampie, your amateur home

+ adult amateur home videos (http://www.planet-lexus.com/forum/index.php?showuser=2498)
- **** amateur home made
+ best nude amateur (http://agat-prestige.ru/forum/index.php?action=profile;u=146648)
- real amateur *** tape
+ amateur female photos (http://gamesplashforum.feen.pl/profile.php?mode=viewprofile&u=944)
- kenwood amateur radio equipment
+ free amateur pussy (http://www.cedriclefebvre.net/forum/profile.php?mode=viewprofile&u=313)
- parejas amateur
+ amateur titfuck (http://vb1.siteirani.com/member31368.html)
- amateur rocket motor construction

d. amateur *** toys, free amateur cfnm, video amateur masturbation
e. amateur anal licking, lingerie amateur, peru amateur circus
f. free amateur cams, amateur astronomy, amateur big butt pics

3. mature amateur **** videos free amateur ****

+ amateur fat **** (http://www.billbearing.com/profile.php?mode=viewprofile&u=167738)
- top amateur movies
+ amateur **** wmv (http://premiumgrind.com/forums/index.php?action=profile;u=74643)
- amateur fakes
+ amateur *** tapes (http://artvine3.org/forum/index.php?action=profile;u=85399)
- lesbian amateur homemade
+ free streaming amateur *** videos (http://netquest1.com/index.php?action=profile;u=120460)
- amateur golf tournament
+ best free amateur **** videos (http://www.str8up.co.uk/v2/forum/profile.php?mode=viewprofile&u=160071)
- amateur lesbian masturbation

a. ***y amateur movies, amateur pics vids, homemade amateur creampie
b. amateur big black cock, amateur striptease contest, yutuvu amateur
c. amateur black shemales, amateur redhead ****, italian amateur ***

+ amateur hidden camera *** (http://stavochka.com/G11//profile.php?mode=viewprofile&u=238900)
- curvy amateur girls
+ amateur women video (http://www.testim.co.il/smf/index.php?action=profile;u=12541)
- amateur teen striptease
+ *** amateur girls (http://www.librored.com/foro//profile.php?mode=viewprofile&u=265242)
- adult amateur community
+ renew amateur radio license (http://secretsloseweight.com/forum/index.php?action=profile;u=26857)
- big breasts amateur
+ amateur surgeon walkthrough peter (http://forums.virtualizationnation.net/index.php?action=profile;u=2351)
- dvd amateur

d. amateur granny ****, amateur mature, asian amateur *** tape
e. ladies amateur golf, voyeur amateur free, amateur dick suck
f. rough amateur *** videos, handjob amateur videos, amateur homemade teen videos