PARCURGEREA DE TIP LEE

PARCURGEREA DE TIP LEE

Deseori ne intalnim cu probleme de tipul urmator: fiind dat un graf neorientat, sa se determine drumul de lungime minima (ca numar de muchii) intre nodul x si nodul y. Rezolvarea acestor probleme se face parcurgand graful in latime de la nodul x la nodul y. Aceasta parcurgere este cunoscuta in literatura de specialitate sub denumirea de parcurgerea in latime sau parcurgerea de tip Lee. Parcurgerea se termina in una din urmatoarele doua situatii:

nodul y a fost gasit;

nodul y nu a fost gasit pe nici un drum ce pleaca din nodul x.

In Parcurgerea de tip Lee utilizam o structura de date tip Coada ale carei elemente contin urmatoarele informatii: (numar-nod, adresa-tatalui, numarul-de-muchii-pina-la-nodul-x, adresa-nodului-urmator).

Adresa-nodului-urmator se utilizeaza numai in cazul alocarii dinamice, deoarece in cazul alocarii statice, cand utilizam un vector, elementele Cozii se succed in cadrul vectorului.

Programul pseudocod al parcurgerii de tip Lee (avand ca nod de plecare nodul x) este urmatorul:

Algoritm Lee

Coada vida

pentru i 1,n executa vizit(i) fals sf.pentru

vizit(x) adevarat

d

Coada (x,0,d)

ok fals   

cat timp nodul y nu a fost introdus in Coada si Coada nu e vida executa

(i,ati,d) Coada

cat timp nodul y nu a fost introdus in Coada si mai exista un vecin j al lui i ce nu a fost vizitat executa

vizit(j) adevarat

atj adresa nodului i

Coada (j,atj,d+1)

daca j=y atunci ok adevarat sf.daca

sf.cat timp

sf.cat timp

daca ok=adevarat

atunci scrie lungimea drumul minim dintre nodul x si nodul y

daca e cazul determinam drumul minim de la nodul x la nodul y astfel:

parcurgem Coada de la nodul y la nodul x, mergand pe legaturile de tip tata;

- simultan cream o Stiva a nodurilor de pe drumul minim;

- in final parcurgem Stiva pentru a afisa coordonatele nodurilor de pe drumul minim.

altfel scrie "nu exista drum de la nodul ", x," la nodul ",y

sf.daca

sf.algoritm

Stiva nodurilor de pe drumul minim poate fi evitata utilizand tehnica recursivitatii, caz in care trebuie sa fim foarte atenti pentru ca numarul de noduri de pe drumul minim sa nu fie prea mare depasind astfel stiva de executie a sistemului de operare.

Problema Drept

O reuniune de dreptunghiuri este definita printr-un sir de perechi de numere

(x₁,y₁),( x₂,y₂), .,( x_n,y_n) cu semnificatia:

dreptunghiul D₁ are punctele si (x₁,y₁) drept varfuri opuse;

dreptunghiul D₂ are punctele (x₁,y₁) si (x₂,y₂) drept varfuri opuse;

dreptunghiul D_n are punctele (x_n-1,y_n-1) si (x_n,y_n) drept varfuri opuse.

Fie D = D₁ È D₂ È È D_n. Dreptunghiurile includ laturile lor.

Cerinta

Fiind data perechea de puncte (a,b), (c,d) care sunt incluse in D sa se determine un drum de lungime minima care le uneste, mergand doar paralel cu axele astfel incat orice punct al drumului sa faca parte din D.

Date de intrare

Fisierul de intrare drept.in are n +3 linii cu structura urmatoare:

pe prima linie se afla numarul n de dreptunghiuri;

pe linia a doua se afla numerele intregi a si b separate intre ele de un spatiu;

pe linia a treia se afla numerele intregi c si d separate intre ele de un spatiu;

pe linia i + 3 se afla numerele intregi x_i si y_i separate intre ele de un spatiu (cu i de la 1 la n);

Date de iesire

Pe prima linie a fisierului de iesire drept.out se va scrie lungimea L a drumului minim iar pe urmatoarele L lini se afla cele L coordonate ale punctelor de pe unul din traseele minime in sensul (a,b) catre (c,d).

Restrictii

£ n £

x_i, y_i, a, b, c, d sunt numere intregi din intervalul [-100, 100];

mentionam ca datele din fisierul de intrare drept.in sunt corecte si ca punctele (a,b) si (c,d) sunt unite prin cel putin un drum in D.

Exemplu

drept.in drept.out

5

1 1

1 2

2 2

3 2

3 1

Programul C (aferent problemei Drept

#include <fstream.h>

#include <string.h>

#define lgc 40001

const int nmax=203, delta=101, dx[4]=, dy[4]=;

int x0,y0,xf,yf,xv,yv,x,y,n,xmin,ymin,xmax,ymax;

unsigned int p,u,ok,lg, huge t[lgc];

char huge cx[lgc],cy[lgc], huge a[nmax][nmax];

ofstream fo('drept.out');

void cit()

fi.close();

void rez()

k++;

p++;

void afis(unsigned int q)

int main()

Problema Paianjen

Un paianjen a tesut o plasa, in care nodurile sunt dispuse sub forma unui caroiaj cu m linii (numerotate de la 0 la m-1) si n coloane (numerotate de la 0 la n-1). Initial, oricare doua noduri vecine (pe orizontala sau verticala) erau unite prin segmente de plasa de lungime 1. In timp unele portiuni ale plasei s-au deteriorat, devenind nesigure. Pe plasa, la un moment dat, se gasesc paianjenul si o musca, in noduri de coordonate cunoscute.

Cerinta

Sa se determine lungimea celui mai scurt traseu pe care trebuie sa-l parcurga paianjenul, folosind doar portiunile sigure ale plasei, pentru a ajunge la musca. De asemenea, se cere un astfel de traseu.

Date de intrare

Fisierul de intrare paianjen.in contine:

- pe prima linie doua numere naturale m n, separate printr-un spatiu, reprezentand numarul de linii si respectiv numarul de coloane ale plasei;

- pe a doua linie doua numere naturale lp cp, separate printr-un spatiu, reprezentand linia si respectiv coloana nodului in care se afla initial paianjenul;

- pe linia a treia doua numere naturale lm cm separate printr-un spatiu, reprezentand linia si respectiv coloana pe care se afla initial musca;

- pe linia a patra, un numar natural k, reprezentand numarul de portiuni de plasa deteriorate;

- pe fiecare dintre urmatoarele k linii, cate patru valori naturale l1 c1 l2 c2, separate prin cate un spatiu,

reprezentand coordonatele capetelor celor k portiuni de plasa deteriorate (linia si apoi coloana pentru fiecare capat).

Date de iesire

Fisierul de iesire paianjen.out va contine pe prima linie un numar natural min reprezentand lungimea drumului minim parcurs de paianjen, exprimat in numar de segmente de lungime 1. Pe urmatoarele min+1 linii sunt scrise nodurile prin care trece paianjenul, cate un nod pe o linie. Pentru fiecare nod sunt scrise linia si coloana pe care se afla, separate printr-un spatiu.

Restrictii si precizari

. 1 <= m, n <= 140

. 1 <= k <= 2*(m*n-m-n+1)

. Lungimea drumului minim este cel mult 15000

. Pentru datele de test exista intotdeauna solutie. Daca problema are mai multe solutii, se va afisa una singura.

. Portiunile nesigure sunt specificate in fisierul de intrare intr-o ordine oarecare. Oricare doua portiuni nesigure orizontale se pot intersecta cel mult intr-un capat. De asemenea, oricare doua portiuni nesigure verticale se pot intersecta cel mult intr-un capat.

Exemplu

paianjen.in paianjen.out

Solutia problemei paianjen

Plasa de paianjen se memoreaza intr-o matrice A cu M linii si N coloane, fiecare element reprezentand un nod al plasei. A[i,j] va codifica pe patru biti directiile in care se poate face deplasarea din punctul (i,j): bitul 0 este 1 daca paianjenul se poate deplasa in sus, bitul 1 este 1 daca se poate deplasa la dreapta, bitul 2 - in jos, bitul 3 - la stanga.

Rezolvarea se bazeaza pe parcurgerea matricii si retinerea nodurilor parcurse intr-o structura de date de tip coada (parcurgere BF - algoritm Lee).

Programul C++ aferent problemei paianjen

#include <fstream.h>

#define dcoada 20000

#define dstiva 13000

#define nmax 141

ifstream fi('paianjen.in'); ofstream fo('paianjen.out');

const dx[4]=, dy[4]=;

dm[4]=, db[4]=;

int n,m,lp,cp,lm,cm,x,xx,y,yy,aux,i,j,k,w; unsigned int p,u,d;

unsigned char huge cx[dcoada]; unsigned int t[dcoada];

union huge uni;

void proc()

}; k++;

}; p++;

d=0; while(u) ;

int main()

for(j=1; j<n; j++) ;

uni.a[0][0]=6; uni.a[0][n-1]=12; uni.a[m-1][0]=3; uni.a[m-1][n-1]=9;

for(p=1; p<=k; p++)

for(u=j; u<y; u++) uni.a[i][u] &= db[1];

for(u=y; u>j; u--) uni.a[i][u] &= db[3];

}

else

;

for(u=i; u<x; u++) uni.a[u][j] &= db[2];

for(u=x; u>i; u--) uni.a[u][j] &= db[0];

};

fi.close(); proc(); fo<<d-1<<endl;

for(p=d; p>0; p--) fo<<(int)uni.s[p][0]<<' '<<(int)uni.s[p][1]<<endl;

fo.close(); return 0;

Problema Nebun

Pe o tabla de sah M*N anumite patrate sunt ocupate. Pe un patrat, numit patrat initial, se afla un nebun care poate sa ajunga pe un anumit patrat numit patrat final dupa un anumit numar de mutari. Mentionam ca nebunul poate muta pe un patratel ce se afla pe aceiasi diagonala cu el daca pe traseul mutarii nu se afla nici un patratel ocupat intre pozitia de plecare si pozitia de sosire la momentul efectuarii mutarii.

Cerinta

Scrieti un program care determina numarul minim de mutari prin care nebunul ajunge din patratul initial in cel final precum si traseul nebunului in sensul patrat initial - patrat final.

Date de intrare

Fisierul de intrare nebun.in este alcatuit din mai multe linii astfel:

pe prima linie sunt doua numere naturale M N separate printr-un spatiu, reprezentand numarul de linii si respectiv numarul de coloane al tablei de sah;

pe linia a doua este un singur numar natural NR ce reprezinta numarul de patrate ocupate;

pe urmatoarele NR linii cate doua numere naturale, separate prin spatiu, reprezentand patratele ocupate (primul numar reprezinta linia iar al doilea reprezinta coloana);

pe urmatoarea linie sunt doua numere naturale, separate prin spatiu, ce caracterizeaza patratul initial (primul numar reprezinta linia iar al doilea reprezinta coloana);

pe ultima linie sunt doua numere naturale, separate prin spatiu, ce caracterizeaza patratul final (primul numar reprezinta linia iar al doilea reprezinta coloana);

Date de iesire

Fisierul de iesire nebun.out va contine:

pe prima linie un singur numar Nrmin reprezentand numarul minim de mutari prin care nebunul ajunge din patratul initial in cel final;

pe urmatoarele Nrmin+1 linii cate doua numere naturale, separate prin spatiu, reprezentand traseul nebunului in sensul patrat initial - patrat final (primul reprezinta linia iar al doilea reprezinta coloana).

Restrictii

1 ≤ M, N ≤ 100

Exemplu

Timp maxim de executie/test: 0,1 secunde

Programul C++ aferent problemei nebun

// Problema Nebun

// Pe o tabla de sah m*n anumite patrate sunt ocupate. Dandu-se un patrat

// initial si unul final se cer urmatoarele:

// - sa se determine numarul minim de mutari prin care nebunul ajunge

// din patratul initial in cel final fara a trece prin patrate ocupate;

// - sa se produca la iesire un sir minim de mutari prin care

// se ajunge din patratul initial in cel final.

#include<fstream.h>

#define dmax 102

ifstream f('nebun.in'); ofstream g('nebun.out');

const int dl[4]=;

int dc[4]=;

struct pnodq ;

pnodq q[dmax*dmax/2+2];

int m,n,li,ci,lf,cf,p,u,umin,a[dmax][dmax];

void cit()

f>>li>>ci>>lf>>cf;

f.close();

void rezolv()

ll=ll+dl[i]; cc=cc+dc[i];

};

};

p++;

};

void afis()

pnods s[dmax*dmax/2+2];

int nr=0,r=umin;

g<<a[lf][cf]<<'n';

do

while(r);

while(nr>0)

g.close();

int main()

Problema LBD

Pe un lac se afla doua lebede, dar fiindca lacul este partial inghetat ele sunt separate de gheata. Lacul are forma unui caroiaj dreptunghiular si consta din NxM patrate aranjate sub forma a N linii si M coloane. Unele dintre patrate sunt acoperite de gheata.
Lacul a inceput sa se dezghete treptat - intr-o zi se dezgheata (se transforma in apa) toate patratele acoperite de gheata care ating apa (au o latura comuna cu un patrat reprezentand apa).

Figura urmatoare ilustreaza lacul din exemplu, apoi lacul dupa o zi, apoi lacul dupa doua zile:

Lebedele pot pluti numai pe apa, deplasandu-se din patratul in care se afla intr-un patrat invecinat pe orizontala sau verticala (nu si pe diagonala).

Cerinta
Scrieti un program care sa determine dupa cate zile se pot intalni cele doua lebede.

Date de intrare

Fisierul de intrare lbd.in contine pe prima linie doua numere naturale N si M, separate prin spatiu, cu semnificatia din enunt. Pe fiecare dintre urmatoarele N linii se afla cate M caractere din multimea . Caracterul '.' (punct) reprezinta un patrat cu apa; caracterul X (litera X majuscula) reprezinta un patrat acoperit de gheata; caracterul 'L' reprezinta un patrat in care se afla o lebada.

Date de iesire

Fisierul de iesire lbd.out va contine o singura linie pe care va fi scris un singur numar natural, reprezentand numarul de zile dupa care cele doua lebede se pot intalni.

Restrictii

1<=N, M <=1500

Exemple

Timp maxim de executie/test: 2 secunde

Programul C++ aferent problemei LBD

#include<fstream.h>

#define dmax 1502

int n,m,lp,cp,lf,cf,nz=0,w;

char a[dmax][dmax], b[dmax][dmax];

struct Coada Q[dmax*dmax];

ifstream f('lbd.in'); ofstream g('lbd.out');

const int dl[4]=, dc[4]=;

void cit()

else

}

else a[i][j+1]=lin[j];

f.get();

}

f.close();

for(i=0;i<=n+1;i++) a[i][0]=a[i][m+1]='X';

for(j=0;j<=m+1;j++) a[0][j]=a[n+1][j]='X';

void lee()

if (ll == lf && cc == cf) w=0;

}

p++;

}

void dezghet()

if(nr<4) b[i][j]='.';

}

for(i=0;i<=n+1;i++) for(j=0;j<=m+1;j++) a[i][j]=b[i][j];

void rez()

} while(w);

int main(void)

Lant minim

Algoritmul lui Lee-determina lungimea lanturilor (minime) de la un varf la toate celelalte

#include<fstream.h>

#include<conio.h>

int a[20][20],n,m,viz[100],c[100],ic,sc,prim;

int t[20];

void drum(int i)

void lanturi()

ic++;

lanturi();

}

}

void main()

cout<<endl<<'matricea de adiacente'<<endl;

for(i=1;i<=n;i++)

cout<<endl<<'lungime lanturi incepand de la? '<<endl;

cin>>x;

cout<<'pana la? ';

cin>>y;

ic=sc=1;

c[ic]=x;

viz[x]=1;

lanturi();

cout<<'lantul minim are lungimea '<<viz[y]<<' ';

cout<<endl;

cout<<'vectorul viz '<<endl;

for(i=1;i<=n;i++)

cout<<viz[i]<<' ';

cout<<endl<<'vectorul t '<<endl;

for(i=1;i<=n;i++)

cout<<t[i]<<' ';

cout<<endl<<'drumul este '<<endl;

drum(y);

getch();}

Problema Labirint

Sa se determine lungimea drumului minim intre doua puncte dintr-un labirint precum si acest drum.

Fisierele de test vor contine un labirint in mod text, iar pe ultima linie a fisierului va fi un singur - (minus). Marginile labirintului vor fi marcate de caracterul '$' dolar. Mutarea dintr-un punct in altul al labirintului se poate face doar pe directiile nord, sud, est, vest. Numarul maxim de linii al unui labirint este 200, egal cu numarul maxim de coloane. Toate fisierele de test vor avea un singur punct de start (S) si un singur punct de final (F). De asemenea nu vor exista puncte de iesire in afara labirintului. Programul va afisa in fisierul de iesire urmatoarele informatii:

- pe o singura linie mesajul FARA SOLUTIE (cand nu exista nici un drum de la S la F);

- pe prima linie lungimea minima a drumului gasit, iar pe urmatoarele linii coordonatele punctelor de pe drumul minim in ordinea de la S la F.

Fisierul de intrare se va numi labirint.in, iar fisierul de iesire labirint.out.

Exemplu de input:

$S F$

Exemplu de output: 3

Indicatie:

Consideram labirintul ca un graf neorientat cu 200 X 200 = 40000 noduri. Oricare doua caractere vecine din fisierul de intrare sunt considerate noduri ale grafului ce sunt legate printr-o muchie. Exceptie de la aceasta regula fac cuplurile in care cel putin un caracter este caracterul $ dolar. In cadrul grafului sunt doua noduri speciale, nodul S (start) si nodul F (final), de care parcurgerea de tip Lee tine cont. Conditiile din problema ne asigura de faptul ca parcurgerea de tip Lee duce la aflarea drumului minim intre S si F sau la concluzia ca nu exista nici un drum intre acestea.

Harta

Enunt:

Se considera o harta bidimensionala cu n linii si m coloane (M_ij), impartita, pentru o mai usoara orientare, in patrate de dimensiune 1. Pe harta sunt marcate pozitiile (patratele) unde se gasesc obstacole.

Cerinta

Cunoscand configuratia hartii si pozitia initiala de unde pornim in explorarea hartii se cere numarul minim de pasi facuti pentru atingerea unei pozitii finale specificate, deplasarea facandu-se dupa anumite criterii.

In prezentarea metodei vom folosi posibilitatea deplasarii pe verticala, orizontala si diagonale. 

Varianta 1 - parcurgere BF( Breath First )

Construim matricea asociata care in general are forma:

Fie D_nm, matricea aflata in corespondenta cu matricea A, in care vom retine din cate mutari poate fi atinsa pozitia (i, j).

Fie vectorii dx[] si dy[], pentru cele 8 directii de deplasare:

dx[8] =;

dy[8] =;

In implementare vom folosi un vector de tip coada c[i], (FIFO -"primul intrat - primul servit"

Observatii:

Vectorul coada va avea doua campuri necesare pentru a retine linia si coloana, dimensiunea maxima fiind n m

Bordam matricea Ai,j

for j:=0 to m+1 do

begin

a[0, j]:=-1;

a[n+1, j]:=-1;

end;

for i:=0 to n+1 do

begin

a[i, 0]:=-1;

a[i, m+1]:=-1;

end;

Construirea drumului si a matricei D se face astfel:

Depunem in coada pozitia de pornire

Extragem din coada pozitia curenta [la, ca] (actuala)

Cautam pozitiile viitoare in care ne putem deplasa avand ca plecare pozitia actuala [lv, cv]

Depunem aceste pozitii in coada C prin incrementarea pozitiei adaugate

Fixam pentru extragerea urmatoarea pozitie curenta

C[1].l=x; C[1].c=y; D[x, y]:=1;

pozitie_curenta:=1; pozitie_adaugata:=1;

while (pozitie_curenta<=pozitie_adaugata) do

begin

la:=C[pozitie_curenta].l;

ca:=C[pozitie_curenta].c;

for i:=1 to 8 do begin

lv:=la+dx[i]; cv:=ca+dy[i];

if (M[lv, cv=0) and ( D[lv, cvi=0) then begin

D[lv, cv]=1+D[l, c];

Inc(pozitie_adaugata);

C[pozitie_adaugata].l=lv;

C[pozitie_adaugata].c=cv;

End;

End;

Inc(pozitie_curenta);

End;

Varianta 2 - Alg. Lee clasic

Spre deosebire de algoritmul BF, algoritmul clasic determina lungimea minima a drumului dintre pozitia de pornire (xp, yp) si pozitia finala (xf, yf). Reconstituirea drumului parcurs este posibila printr-o parcurgere de la (xf, yf) spre (xp, yp) si vizitarea vecinilor pentru care valoarea din matricea D este strict mai mica cu o unitate decat valoarea actuala.

Bordam matricea Ai,j

for j:=0 to m+1 do

begin

a[0, j]:=-1;

a[n+1, j]:=-1;

end;

for i:=0 to n+1 do

begin

a[i, 0]:=-1;

a[i, m+1]:=-1;

end;

Construirea matricea D astfel:

Cautam in matricea D toate pozitiile care au fost atinse intr-un acelasi numar de pasi

Pentru fiecare pozitie descoperita determinam viitoarele pozitii

Incrementa numarul de pasi

k:=1;

D[xp,yp]:=k;

repeat

vb:=false;

for i:=1 to n do

for j:=1 to m do

begin

if D[i,j]=k then begin

for x:=1 to 8 do

begin

lv:=i+dl[x];

cv:=j+dc[x];

if (D[lv,cv]=0) and (A[lv,cv]=0) then

begin

D[lv,cv]:=k+1;

if (lv=xf)and(cv=yf) then

write(D[lv,cv]);

vb:=true;

end;

end;

end;

end;

if vb then k:=k+1;

until not vb;