Algoritmul lui Lee [need help ]

[•Petrucci]

off..an nevoie, de Algoritmul lui Lee implementat de preferat in c++. Mentionez ca sunt elev in clasa a X-a..
Va rog,ajutati pe cei sa saraci cu duhul ca mine.

[•alexandru92]

Daca cauti  pe  net  o sa  gasesti uite : http://infoscience.3x.ro/c++/Algoritmul_lui_Lee.htm
sau  http://www.ginfo.ro/revista/15_2/focus1.pdf   iti zic  sincer  nu prea  stiu  ce  face nici n-am auzit dar  am dat shearch pe  google

[•toni2007]

Uite un exemplu, am presupus ca tu vrei sa ajungi din start in end, si ai unele casute prin care nu poti trece, marcate cu '#' (diez).

Cod:

#include <queue> // pt queue
#include <algorithm>  // pt pair
#define mkp make_pair
#define ff first
#define ss second
#define punct pair<int,int>

using namespace std;

int A[1000][1000], D[1000][1000];

punct start, end;

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

int lee(){
	int i;
	
	initializare(); // initializam matricea D cu infinit, marginile cu -1 si punctul de inceput cu 0
	
	queue<punct> Q;
	punct now, now2;
	
	Q.push(start);	// bagam punctul de inceput in coada
	
	while (Q.empty() == false){			// cat timp coada nu e vida
		now = Q.front(); Q.pop(); // eliminam nodul din fata din coada
		if (now == end) // daca se poate returnam minimul
			return D[end.ff][end.ss];
		for (i = 0; i < 4; ++i){	// parcurgem vecinii
			now2 = mkp(now.ff + dx[i], now.ss + dy[i]);
			if (D[now2.ff][now2.ss] > D[now.ff][now.ss] + 1 && A[now2.ff][now2.ss] != '#'){
				// daca se poate ajunge cu cost mai bun si nu e ocupata casuta (sa zicem ca unele casute sunt ocupate, depinde de enuntul problemei
				D[now2.ff][now2.ss] = D[now.ff][now.ss] + 1; // modificam costul
				Q.push(now2);	// bagam in coada nodul curent
			}
		}
	}
	
	return -1; //daca se ajunge aici inseamna ca nu se poate ajunge la destinatie 
	
}

Spor

[•Petrucci]

  Merci mult !

[•Cosmin]

Ce cauti tu se numeste algoritmul de cautare in latime. Nu exista algoritmul lui Lee cel putin el nu se refera la acest algoritm. Din pacate a intrat in constiinta publica a profesorilor din romania dupa ce acest algoritm a fost numit asa in una din cartile de probleme de algoritmica de la inceputul anilor 90.

Arhiva educationala are o problema in care e explicat algoritmul si daca te uiti la solutii poti vedea diverse implementari de 100 de puncte. Poti sa gasesti aici problema http://infoarena.ro/problema/bfs

Si pentru ceilalti, in loc sa hranim userii cu informatie mura in gura, e mai bine cateodata sa popularizam sectiuni ale siteului infoarena  care ii ajuta sa isi rezolve problemele.

[•sigrid]

Si pentru ceilalti, in loc sa hranim userii cu informatie mura in gura, e mai bine cateodata sa popularizam sectiuni ale siteului infoarena  care ii ajuta sa isi rezolve problemele.

A da cuiva "mura in gura" inseamna (in acest context) a-l ajuta pe celalalt, a pune la share ceea ce tu deja stii. De ce sa nu vrei sa ajuti sau sa explici atunci cand ti se solicita ajutorul sau explicatia? Sunt convinsa ca (mai ales utilizatorii noi care fac cont doar pentru a intreba despre o tema si apoi nu mai intra niciodata -poate- pe Infoarena) daca ar vrea o colectie de link-uri (folositoare) legate de intrebarea pe care o ridica ar da simplu search pe Google.

E o diferenta intre a interactiona cu oamenii, a purta o discutie, a oferi lamuriri, a putea intoarce o intrebare in caz de noi nelamuriri care se ivesc si a "te descurca" singur cu un site. Eu de cele mai multe ori prefer sa intreb pe cineva dispus sa-si faca timp sa-mi raspunda decat sa "sap" singura. Si cred ca cei mai multi suntem asa.

Raspunsul tau, de exemplu, mi s-a parut perfect inainte sa citesc precizarea pe care am citat-o. Ofera informatii suficiente si daca cel care a avut probleme considera ca-l poti ajuta mai departe te va intreba probabil si ce este cautarea in latime. Strecori printre randuri si un link folositor care duce intr-o alta sectie Infoarena. La final vii cu aceata precizare, careia ii vad logica, dar nu-i vad rostul intr-un topic, intr-un forum chiar, in care de cele mai multe ori raspunsurile sunt complete, tastate "de mana" si oferite cu bunavointa.

Cu respect,
Maria Stanciu

[•alexandru92]

@Stanciu Maria   nu vreau sa te supar dar  nu prea vad rostul comentului tau

[•sigrid]

Alexandru, comentariu meu era pentru cei care ii vad rostul.

Pentru restul el poate intra, ca si al tau, in categoria posturilor menite sa creasca numarul de posturi. Nu m-ai suparat cu nimic, nu-ti face griji .

[•alexandru92]

in categoria posturilor menite sa creasca numarul de posturi

Pe oirce forum  intru, un doi vad aceasta  replica care ma scoate din nervi  cu ce ma ajuta  ca imi cresc posturile, ma ajuta sa o gasesc pe  zana maseluta, o comoara ascunsa daca am nr posturi = 500000, sau?...e o replica de adreptu lipsita de rost si sa nu zic altfel.

[•devilkind]

Cred ca Cosmin se referea la un alt post care m-a deranjat oarecum si pe mine si chiar ma intrebam daca sa il sterg sau nu, mai exact postul lui Toni, care a pus acolo o implementare directa pe care daca o copiezi pur si simplu iti va rezolva problema insa nu vei intelege nimic. Exact ceea ce inseamna "a da mura in gura".

Anyway discutia devine offtopic.

[•sigrid]

Uite tocmai (cum zici si tu) ca Toni a pus mai sus o implementare directa ce poate fi folosita, chestie care in fond este exact ceea ce Dascal Cezar a cerut prin acest topic: "Algoritmul lui Lee implementat de preferat in c++". Chiar te-a suparat ca i-a raspuns  ? Astfel de implementari se mai gasesc pe net, a sterge postul de mai sus nu este o solutie pentru a evita fenomenul de a da copy-paste fara sa intelegi ceva.

Imi pare rau ca am dus discutia in offtopic, daca prin asta creez neplaceri moderatorilor. Si imi pare rau ca nu inteleg de ce priviti asa lucrurile.

[•toni2007]

Omul a cerut un algoritm in C++, i-am dat ce a cerut, i-am comentat toata sursa (cred ca mai mult din jumatate din sursa sunt comentarii), pentru a intelege ce face sursa. Daca el da copy paste la sursa e problema lui, nu vad de ce ar trebui sa ne pierdem noi timpul intr-un mod foarte useless pentru a ne intreba ce face el cu codul postat de mine. Sunt convins ca daca omul chiar ar fi vrut sa aiba mura in gura ar fi dat un post pe softpedia sau orice forum d-asta cu sute de useri online odata, unde intrebi ceva si in 10 minute ti-au raspuns deja 3 oameni, si ar fi obtinut raspunsul.

Numai bine,

Toni

[•alexandru92]

Pentru a  termina  cu datul  "mura in  gura", ar trebui  inceput din scola  unde proful da  algoritum  , toti il tocesc , 99%- nu-l inteleg si de aceea desi il stiu  n-au habar  cum sa-l aplice, plus oricene vera da la google un shearch si ai  vreo 100 de exmple cu acel algrotim deci este  inutil
And lets stop with this.... ok?

[•chera_lary]

editat de moderator: nu postati solutii complete la problemele din arhiva.

Ii felicit pe toti ce isi pierd timpul pentru a solutiona si a explica probleme pe acest forum! Le voi mai adauga tuturor cate un punct la Karma. Mie mi se pare "ok" postarea codurilor integral si in acelasi timp explicate, cel putin postul lui toni mi s-a parut ok si nu era foarte greu de inteles.
Imi cer scuze ca am postat problema respectiva! Am vrut doar sa fiu de ajutor! Era o implementare fara "stl".

[•sima_cotizo]

In loc de rezolvarea integrala puteai sterge din sursa bucati incat sa ramana doar partea necesara a algoritmului. Nu strica "bucuria" altor participanti de a rezolva singuri unele probleme / de a descoperi metodele prin care se rezolva. Pentru problemele din arhiva nu se posteaza solutii integrale, iar daca vrei sa ajuti o poti face postand doar partea "care trebuie".

---

Cred ca discutia devine off-topic si in afara de vreo 2 posturi, restul nu isi au locul aici. Haideti sa nu o continuam inutil.