Algoritmul Lee

Imi poate explica cineva algoritmul lui Lee pentru aflarea distantei minime dintre 2 puncte ?

Cristi212, on 30th January 2010, 23:03, said:

/* Probleme de drumuri minime.
a) Determinarea numarului minim de pasi. ( sau a lungimii drumului ).
Pt o matrice : c[DIM][DIM];
unde c[i][j] reprezinta numarul de pasi minimi de la c[ip][jp] pentru a ajunge la c[i][j]
Distanta Manhattan ( daca nu sunt obstacole )
Algoritmul Lee ( daca exista obstacole )
 */
#include <fstream>
using namespace std;
#define INF 9999

int a[100][100];
int c[100][100];
int ip, jp, is, js;
int m, n;
const int di[] = { -1, 0, 1, 0 },
	dj[] = { 0, 1, 0, -1 };
	
bool OK( int i, int j );
void Lee();
void Write();

int main()
{
	Read();
	Lee();
	Write();
	
	return 0;
}   

void Read()
{
	ifstream fin("lee.in");
	fin >> n >> m;
	fin >> ip >> jp >> is >> js;
	for ( int i = 0; i < n; i++ )
		for ( int j = 0; j < m; j++ )
		{
			fin >> a[i][j];
			c[i][j] = INF;
		}	
	fin.close();
}	 

bool OK
{
	if ( a[i][j] == 1 ) return false; // obstacol, marcat de cifra 1 aici.
	if ( i < 0 || j < 0 || i >= n || j >= m )
		return false; // in afara matricei
	return true;  // niciuna din conditiile de mai sus nu au fost adevarate.
}	

void Lee
{
	c[ip][jp] = 0; // punctul de plecare. distanta pana la el fiind de 0.
	bool modif; 
	int pas = 0; // numarul de pasi efectuati.
	do 
	{
		modif = false;
		for ( int i = 0; i < n; i++ )
				for ( int j = 0; j < m; j++ )
					if ( c[i][j] == pas ) // verificam numarul de pasi incrementat anterior sau 0 pentru a-i stabili vecinii.
// in continuare verifici vecinii pozitiei pe care te aflii. 
						for ( int d = 0; d < 4; ++d )
						{
// le calculezi numarul de pasi necesari pentru a ajunge de la c[ip][jp] ( unde ip = linia de pornire si jp = coloana de pornire ) pana la c[i][j].
							int iv = i + di[d];
							int jv = j + dj[d];
							if ( OK( iv, jv) )
							{
								c[iv][jv] = pas + 1;
								modif = true;
								if ( iv == is && jv == js ) // cand ajungi la destinatie te opresti.
									return;
							}
						}		
		pas++;
	} while ( modif );	
}	

void Write()
{
	for ( int i = 0; i < n; i++ )
	{
		for ( int j = 0; j < m; j++ )
				fout << c[i][j] << ' ';
		fout << '\n'
	}
	fout >> c[is][js];	
		
	
}

Eu l-am scris, sper sa intelegi. Mai bine de atat eu nu pot explica doar daca esti in fata mea.

Edited by softpedian, 31 January 2010 - 03:10.

Mersi,am inteles insa am cateva intrebari :
De ce in matricea c[][] am numai valoarea : drum-minim(adica valoarea lui pasi de la final ) sau drum-minim -1 (si INF pentru obstacole)?

Edited by Cristi212, 07 February 2010 - 12:39.

Va mai avasez cu intrebari ca...sunt nu chiar foarte la inceput dar...nu prea ma descurc cu algoritmii complicati. Unul dintre ei pe care l-am detestat de cand am facut cunostinta cu el...este lee.
Am facut o functie care trebuie sa calculeze drumul minim intr-o matrice intre 2 obstacole. Matricea e bordata cu -1, obstacolele sunt -2. Functia este apelata de mai multe ori in timpul unei executari. Drumul nu are voie sa iasa din matrice sau sa dea peste obstacole...dar are voie sa se suprapuna peste alte...drumuri. Postez doar functia lee care...merge doar cand are chef (adica pe unele valori merge (si da bine), pe altele...crapa programul). c e coada definita pe o structura (mat) cu 2 proprietati sa le zic asa...x si y. De ce imi da eroare?

int lee(int x1, int y1, int x2, int y2){
mat c[10000];
int p, i;

c[0].x=x1;
c[0].y=y1;
a[x1][y1]=1;

p=1; i=0;
while((!(c[i].x==x2 && c[i].y+1==y2)) && (!(c[i].x==x2 && c[i].y-11==y2)) && (!(c[i].x+1==x2 && c[i].y==y2)) && (!(c[i].x-1==x2 && c[i].y==y2))){
if(a[c[i].x+1][c[i].y]==0){
c[p].x=c[i].x+1;
c[p].y=c[i].y;
a[c[i].x+1][c[i].y]=a[c[i].x][c[i].y]+1;
p++;
}
if(a[c[i].x-1][c[i].y]==0){
c[p].x=c[i].x-1;
c[p].y=c[i].y;
a[c[i].x-1][c[i].y]=a[c[i].x][c[i].y]+1;
p++;
}
if(a[c[i].x][c[i].y+1]==0){
c[p].x=c[i].x;
c[p].y=c[i].y+1;
a[c[i].x][c[i].y+1]=a[c[i].x][c[i].y]+1;
p++;
}
if(a[c[i].x][c[i].y-1]==0){
c[p].x=c[i].x;
c[p].y=c[i].y-1;
a[c[i].x][c[i].y-1]=a[c[i].x][c[i].y]+1;
p++;
}

i++;
}

return p;
}

Un prim bug care  l-am observat e in conditia de while:  c[i].y-11==y2 care cred ca ar trebui sa fie c[i].y-1
Si ziceai ca apelezi funcita de mai multe ori asta insemnand ca ai deja drumuri scrise pe matrice si vor "interfera" unele cu altele. Ca sa eviti asta ar fi mai util sa ai 2 matrici (una cu obstacole si una pe care faci drumul pe care o initializezi cu 0 de fiecare data); presupunand ca v[n][n] e matricea drumurilor la fiecare apelare a functiei ar trebui sa scrii si memset (v,0,sizeof(v)).

Ponturi:
1) in loc sa lucrezi cu c[i].x si c[i].y, declarati niste variabile (xx=c[i].x si yy=c[i].y) pentru a fi mai 'inteligibil' codul;

2) ca sa nu scrii 4 if uri declara:
int const dx[]={0, 0,0,1,-1};
int const dy[]={0,-1,1,0, 0};
presupunand ca esti in nodul de coordonate x si y si mergi in xx si yyvei avea:
xx=x+dx[i];
yy=y+dy[i];

#include<fstream>
using namespace std;
int a[100][100],v[100][100];
int m,n;
//xi yi=pozitiile initial
//xf,yf=pozitiile finale
//m,n dimensiunile matricii
const int dx[]={0,0,0,1,-1};
const int dy[]={0,1,-1,0,0};
//am presupus ca se poate merge in 4 directii: sus, jos, st,dr
int cx[400],cy[400];
//coada
int lee(int xi,int yi,int xf,int yf)
{
	int f,b,x,y,xx,yy,i;
	memset(a,0,sizeof(a));
	b=1;
	f=1;
	cx[f]=xi;
	cy[f]=yi;
	while (f<=b)
	{
		x=cx[f];
		y=cy[f];
		f++;
		for (i=1;i<=4;i++)
		{
			xx=x+dx[i];
			yy=y+dy[i];
			if (xx==xf&&yy==yf)
				return a[x][y]+1;
			//nu fac bordare si verific daca cooronatele se afla in matrice
			if (xx>0&&yy>0&&xx<=n&&yy<=m)
			{
				//verific daca locul respectiv e liber si daca casuta nu a mai fost vizitata
				if (v[xx][yy]==0&&a[xx][yy]==0)
				{
					a[xx][yy]=a[x][y]+1;
					b++;
					cx[b]=xx;
					cy[b]=yy;
				}
			}
		}
	}
	return a[xf][yf];
}
int main()
{
	int i,j,q,xi,yi,xf,yf;
	//q=numarul de querry uri pt lungimea drumurilor
	ifstream in("lee.in");
	ofstream out("lee.out");
	in>>n>>m>>q;
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
			in>>v[i][j];
	for (i=1;i<=q;i++)
	{
		in>>xi>>yi>>xf>>yf;
		out<<lee(xi,yi,xf,yf)<<'\n';
	}
}

Edited by tinky, 11 April 2011 - 22:58.

Multumesc pentru tip-uri. Acel 11 era pus din greseala , da...trebua -1.
Una din probleme era faptul ca se cam intalneau drumurile (am rezolvat asta punand obstacolele cu -1...si citeam matricea si unde era numar pozitiv pun 0). Mai am niste bug-uri de rezolvat dar...am scapat de lee .

Multumesc din nou.

Gata..nu mai pot.  Problema asta imi mananca nervii de cateva zile. initial nu prea pricepusem eu lee...acum...nu stiu ce sa ii mai fac. Deci...se da o matrice. unde e X e blocat. unde e . se poate trece (eu le inlocuiesc cu -1 si 0). se da un sir de date de forma x1 y1 x2 y2, unde x1 y1 sunt coordonatele primului obstacol...iar x2 y2 coordonatele obstacolului la care trebuie sa ajung. setul de date se termina cu 0 0 0 0. Postez un exemplu de date de intrare si programul. care e problema? pai...la ultimul set de date (de fapt la penultimul...ultimul e  0 0 0 0) trebuie sa se blocheze si sa afiseze 0. se blocheaza...numai ca nu stiu cum naiba apare din senin un 1 pe undeva pe marginea din stanga :|.
Apropo...nu am avut timp sa implementez sfaturile de mai sus...si nu am vrut sa dau chiar copy-paste, sa inteleg si eu ce e acolo. Imi cer scuze pentru asta.
Revenind...v-as ramane profund indatorat daca mi-ati explica ce se intampla.

#include<fstream.h>
#include<iostream.h>

ifstream f("inginer.in");
ofstream g("inginer.out");

int m, n, a[76][76], i, p=0;

typedef struct{
	int x; 
	int y;
}mat;

mat c[10000];

void down(){
	c[p].x=c[i].x+1; 
	c[p].y=c[i].y;
	a[c[i].x+1][c[i].y]=a[c[i].x][c[i].y]+1;
	p++;
}
void up(){
	c[p].x=c[i].x-1;
	c[p].y=c[i].y;
	a[c[i].x-1][c[i].y]=a[c[i].x][c[i].y]+1;
	p++;
}
void right(){
	c[p].x=c[i].x;
	c[p].y=c[i].y+1;
	a[c[i].x][c[i].y+1]=a[c[i].x][c[i].y]+1;
	cout<<c[p].x<<" "<<c[p].y<<" right"<<"\n";
	p++;
}
void left(){
	c[p].x=c[i].x;
	c[p].y=c[i].y-1;
	a[c[i].x][c[i].y-1]=a[c[i].x][c[i].y]+1;
	p++;
}

//Lee algorithm
int lee(int x1, int y1, int x2, int y2){

	i=0; p=1;
	
	c[0].x=x1;
	c[0].y=y1;

	if(a[x1][y1]==0 || a[x2][y2]==0){
		return 0;
	}else{
		a[x1][y1]=1;
		while((!(c[i].x==x2 && c[i].y+1==y2)) && (!(c[i].x==x2 && c[i].y-1==y2)) && (!(c[i].x+1==x2 && c[i].y==y2)) && (!(c[i].x-1==x2 && c[i].y==y2))){
			if(a[c[i].x+1][c[i].y]==0 && c[i].x+1<=m+1){
				down();
			}
			if(a[c[i].x-1][c[i].y]==0 && c[i].x-1>=0){
				up();
			}
			if(a[c[i].x][c[i].y-1]==0 && c[i].y-1>=0){
				left();
			}
			if(a[c[i].x][c[i].y+1]==0 && c[i].y+1<=n+1){
				right();
			}
						
			if(p==i){
				return 0;
			}
			i++;
					
		}
	}
	return a[c[i].x][c[i].y];
}


int main(){
	
	char k;
	int ok2, x1, y1, x2, y2;
	
	f>>m>>n;
	
	for(int i=1; i<=m; i++){
		for(int j=1; j<=n; j++){
			f>>k;
			if(k=='X'){
				a[i][j]=-1;
			}else{
				a[i][j]=0;
			}
		}
	}
	
	ok2=1;
	while(ok2){
		f>>x1>>y1>>x2>>y2;
		if(x1!=0 && x2!=0 && y1!=0 && y2!=0){
			g<<lee(x1, y1, x2, y2)<<"\n";
			for(int i=0; i<=m+1; i++){
				for(int j=0; j<=n+1; j++){
					if(a[i][j]>0){
						a[i][j]=0;
					}
					a[x1][y1]=-1;
				}
			}
		}else{
			ok2=0;
		}
	}
	
	f.close();
	g.close();
	
	return 0;
	
}

Si datele de intrare:

4 5
XXXXX
X...X
XXX.X
.XXX.
3 2 3 5
3 1 4 4
3 2 4 3
0 0 0 0

O prima problema destul de grava e ca ai declarat i si p atat global cat si local in functia Lee.

PS: e un pas spre bine ca ti ai facut functii pentru up right left down  

Pai...nu prea le-am declarat decat global. in lee doar le initializez cu o si respectiv, 1.

mea culpa.. nu m-am uitat atent

Salut!! Am o intrebare, imi puteti arata si mie algoritmul de " Fill " si algoritmul " Lee ".NU stiu in ce constau dar am vazut la mai multe probleme de a X-a pe .campion ca se folosesc,dar nu prea am gasit pe internet nimic folositor de unde sai invat....HELP??

Ai cautat de te-ai spart:
http://en.wikipedia....wiki/Flood_fill
http://en.wikipedia....i/Lee_algorithm

Nu te doare mana de atata cautat?
Ca mie 12 secunde mi-a luat sa iti scriu acest post!

Edited by Paullik, 16 August 2011 - 18:35.

Paullik, on 16th August 2011, 19:35, said:

Nu-ti bate capul cu ambele, invata "Lee"  si gata, Flood-fill nu-i mic mai mult decat versiunea recursiva.

Paullik, on 16th August 2011, 19:35, said:

Bine asta am gasit si eu,dar am vrut ceva implementat in c++ si un exemplu pe o problema sau ceva ca sa inteleg mai bine eu am zis ca nu am gasit ceva folositor.....

Mitza444, on 16th August 2011, 22:10, said:

Odata ce intelegi algoritmul, poti sa faci si singur implementarea.
Uite cateva probleme :
http://infoarena.ro/problema/alee
http://infoarena.ro/problema/insule
http://infoarena.ro/problema/muzeu
http://infoarena.ro/problema/rj
http://fiicompetitio...t_safeu_3_8.pdf
Majoritatea care cer aflarea drumului minim pintr-o matrice

OK, m-am uitat pe explicatia de pe wikipedia a algoritmului Lee si dupa am vrut sa rezolv problema insule,dar nu am nici o idee :|
E cam vaga explicatia pe wikipedia a algoritmului si nu am inteles mai nimic....

Edited by Mitza444, 17 August 2011 - 14:18.

Nu incepe cu insule, nu e chiar asa simpla. Fa alee, e clasica .
Algoritmul lee este urmatorul :

//consideram ca trebuie sa plecam din casuta( 0, 0 ) si trebuie sa ajungem in casuta ( N, M )
1. Adaugam nodul (0, 0 ) in coada
2. Marcam nodul (0, 0) ca fiind vizitat
3. Setam distanta de la nodul (0, 0) la (0, 0) ca find 0
4. Cat timp coada nu este goala si nodul (N, M) este marcat ca nevizitat
	   5. Se extrage un nod din coada
	   6. Pentru fiecare vecini din coada
			 7. Verificam daca  n-a fost vizitat 
					 8. In caz ca n-a fost vizitat, se adauga in coda
					 9. Distanta de la nodul (0,0) la acest vecin este distanta de la nodul extras+1

                  
Plus parca pe forum s-a mai vorbit despre acest algoritm, fa un search si vezi, analog pe forumul infoarena.ro