Algoritmul Lee

Bun am inceput sa inteelg cum sta treaba cum algoritmul lui Lee,dar am cateva intrebari:
1.La coada trebuie sa folosesc #include<queue> sau pot un vector simplu pentru ca <queue> nu stiu sa folosesc??
2.In coada trebuie sortate nodurile sau cum??
3.De unde stiu care nod din coada trebe extras urmatorul??

Mitza444, on 18th August 2011, 13:30, said:

Coada este un vector cu propietatea ca elementele se adauga la sfarsit si se extrag de la inceput. Am zis eu undeva ca trebuie sortate elementele ? Daca sti sa lucrezi cu STL poti folosi queue, altfel foloseste un vector obisnuit.

Edited by secretalex92, 18 August 2011 - 13:18.

secretalex92, on 18th August 2011, 14:18, said:

Aha deci daca am o valoare x care sa o pun in vector in loc sa zic v[1]=x zic v[n]=x(n este ultimu element)

Mitza444, on 18th August 2011, 15:04, said:

Da, de fiecare datã când adaugi un element îl vei adãuga pe poziția "n", unde "n" este numãrul de elemente din vector.

De fiecare datã când extragi un element îl extragi de pe poziția "0". ⁽¹

O coadã implementatã în C++ (adicã clasã) ar trebui în principiu sã aibã metoda Enqueue() ⁽², Dequeue() ⁽³ și Peek() ⁽⁴ pentru a putea fi utilã (denumirile pot fi schimbate).

O coadã are reprezentarea asemãnãtoare, și foarte des comparatã, cu o coadã de la magazin. Funcționeazã pe principiul "Primul venit, primul servit" (sau First In First Out - FIFO).

---
(¹ Presupunând cã poziția 0 corespunde primului element.
(² Metoda adaugã un element în coadã - conform regulii pe ultima poziție.
(³ Metoda scoate primul element din coadã.
(⁴ Permita vizualizarea primului element fãrã a îl scoate.

Pentru a folosi o implementare deja existentã vezi : http://www.sgi.com/tech/stl/queue.html sau http://www.cplusplus...ence/stl/queue/

Succes!  

Se pot implementa cozi pe vector fara sa ne complicam cu extractia primului element (stiu...metoda e ineficienta dar pentru un incepator e ok). Practic tu ce faci. fie casuta k, casuta de inceput. coada este vectorul q. i, j sunt 2 variabile, initializate cu 0. i este elementul curent, si j este elementul pe care il analizam.

q[0]=k;
i++;

acum analizam elementul q[j] (j=0), si introducem in coada (cu conditia ca elementele sa fie libere-daca avem obstacole), elementul de deasupra, de dedesubt, din stanga si pe cel din dreapta. dupa fiecare element introdus, marim pe i. apoi incrementam pe j cu 1, si luam iar q[j], si introducem cele 4 elemente (daca acestea sunt libere). si tot asa...pana ajungem intr-o pozitie invecinata cu pozitia cautata.

Se folosesc 2 vectori, unul pentru x si unul pentru y.

Am ajuns de la lee/fill la cozi/stacks.
Frumos offtopic-ul.

Gady_paul, on 18th August 2011, 19:13, said:

Nu am inteles nimic, te-ai exprimat ca ... pixu'.

Ce e asa greu domne sa extragi un element din vector?

Daca ai vectorul cu continutul:

n=4
a b c d
0 1 2 3

Ca sa-l scoti pe 'a' muti pur si simplu fiecare element din dreapta o pozitie la stanga si scazi 1 din marimea vectorului:

n=3
b c d
0 1 2

La fel pt orice pozitie, nu numai pozitia 0, cu conditia ca 0 <= poz < n, unde n este marimea vectorului.

Hai gata cu offtopic-ul.

Edited by Paullik, 18 August 2011 - 20:12.

@Paullik Nu e nimic greu cu stergerea unui element dintr-un vector, dar de ce sa o faci cand nu e nevoie ? Si hai sa nu-l lasam pe initiator intr-o ceata si mai mare. Ii sugerez sa implementeze ce a zis Gray_Paul, asa se face in practica de cele mai multe ori( el sugereaza sa tinem minte doi indexi reprezentand inceputul si sfarsitul cozii restul cred ca e evident ), e simplu si eficient.
Si ai dreptate, deja e prea offtopic  

Edited by secretalex92, 18 August 2011 - 20:36.

Eh, in primul rand e o optimizare considerabila sa si elimini elementele din fata vectorului, cand limita de memorie este importanta. Dar, folosind C-ul (adica trebuie sa faci o functie care sa elimine primul element), pe matrici mari, este ineficient dpdv al timpului de executie. Nu stiu cu cat e mai rapid queue, dar banuiesc ca este mai rapid decat sa copiezi un vector destul de mare. Oricum, ca incepator, e bine sa nu le elimini.

Acum intreb si eu, care e diferenta (atat dpdv algoritmic cat si practic) dintre fill si Lee?

Am reusit sa implementez un algoritm pentru problema alee si pe exemplu imi da rezultatul dar cand il bag pe infoarena sau .campion imi da peste tot killed by signal 11  

#include<cstdio>
using namespace std;
int mat[200][200],N,M,x,y,x1,y1,x2,y2,pas=1,i,j,d;
const int di[] = { -1, 0, 1, 0 },dj[] = { 0, 1, 0, -1 };
bool OK(int k,int p){
	if(mat[k][p]!=0){return false;}
	if(k<0 || p<0 || k>N || p>N){
		return false;}
	return true;
}
void Lee(){
	bool modif;
	do
	{
		modif=false;
		for(i=1;i<=N;i++){
			for(j=1;j<=N;j++){
				if(mat[i][j]==pas){
					for(d=1;d<=4;d++){
						int iv=i+di[d];
						int jv=j+dj[d];
						if(OK(iv,jv)){
							mat[iv][jv]=pas+1;
							modif=true;
							if(iv==x2 && jv==y2){
								return;}
						}
					}
				}
			}
		}
		pas++;
	}while(modif);
}

	
int main(){
	FILE * pFile;
	pFile=fopen("alee.in","r");
	fscanf(pFile,"%d%d",&N,&M);
	for(i=1;i<=M;i++){
		fscanf(pFile,"%d%d",&x,&y);
		mat[x][y]=-1;
	}
	fscanf(pFile,"%d%d%d%d",&x1,&y1,&x2,&y2);
	mat[x1][y1]=1;
	Lee();
	pFile=fopen("alee.out","w");
	fprintf(pFile,"%d",pas+1);
	return 0;
}

Ceva idei???

Pai pentru ca vectorii di si dj sunt indexati de la 0 , nu de la 1. Dar de ce nu folosesti o coada, in loc sa parcurgi de fiecare data matricea N, M sa vezi ce casuta trebuie prelucrata ?

Edited by secretalex92, 19 August 2011 - 16:58.

secretalex92, on 19th August 2011, 17:57, said:

Da cred ca ar trebui sa folosesc o coada pentru ca imi pica la timpu de executie la un test
Dar pentru o coada nu mi-ar mai trebui inca o matrice in care sa retin toate coordonatele punctelor din coada(nu ar pica la memorie??)
Si daca as folosi o coada as incepe asa nu: coada[1][1]=x1 , coada[1][2]=y1 ??

Pai folosesti o matrice de char si pui coada de short int. Ar trebuii sa incapa.

Am incercat sa fac o coada pe o matrice in care am retinut x si y ,dar nu functioneaza....

#include<cstdio>
using namespace std;
#define Nmax 175
int mat[Nmax][Nmax],c[Nmax*Nmax][3],N,M,x,y,x1,y1,x2,y2,p,u,xnou,ynou,d,i,j;
const int di[] = { -1, 0, 1, 0 },dj[] = { 0, 1, 0, -1 };
bool OK(int k,int q){
	if(mat[k][q]!=0){return false;}
	if(k<1 || q<1 || k>N || q>N){
		return false;}
	return true;
}
void Lee(){
	c[1][1]=x1;c[1][2]=y1;
	for(p=1,u=1;p<=u;p++){
		x=c[p][1];
		y=c[p][2];
		for(d=0;d<4;d++){
			xnou=x+di[d];
			ynou=y+dj[d];
			if(OK(xnou,ynou)){
				mat[xnou][ynou]=p+1;
				c[++u][1]=xnou;
				c[u][2]=ynou;
				if(xnou==x2 && ynou==y2){
					return;
				}
			}
		}
	}
}
int main(){
	FILE * pFile;
	pFile=fopen("alee.in","r");
	fscanf(pFile,"%d%d",&N,&M);
	for(i=1;i<=M;i++){
		fscanf(pFile,"%d%d",&x,&y);
		mat[x][y]=-1;
	}
	fscanf(pFile,"%d%d%d%d",&x1,&y1,&x2,&y2);
	mat[x1][y1]=1;
	Lee();
	pFile=fopen("alee.out","w");
	fprintf(pFile,"%d",mat[x2][y2]);
	return 0;
}

Edited by Mitza444, 20 August 2011 - 10:31.

Bun am reusit sa fac cum ai zis cu coada,dar acuma din nou pica la timpul de executie,dar nu la acelasi test ci la altul
Ce sa fac??

#include<cstdio>
using namespace std;
#define Nmax 175
int mat[Nmax][Nmax],c[Nmax*Nmax][3],N,M,x,y,x1,y1,x2,y2,p,u,xnou,ynou,d,i,j,m;
const int di[] = { -1, 0, 1, 0 },dj[] = { 0, 1, 0, -1 };
bool OK(int k,int q){
	if(mat[k][q]!=0){return false;}
	if(k<1 || q<1 || k>N || q>N){
		return false;}
	return true;
}
void Lee(){
	c[1][1]=x1;c[1][2]=y1;
	for(p=1,u=1;p<=u;p++){
		m=u;
		for(j=p;j<=m;j++){
		x=c[j][1];
		y=c[j][2];
		for(d=0;d<4;d++){
			xnou=x+di[d];
			ynou=y+dj[d];
			if(OK(xnou,ynou)){
				mat[xnou][ynou]=p+1;
				c[++u][1]=xnou;
				c[u][2]=ynou;
				if(xnou==x2 && ynou==y2){
					return;
				}
			}
		}
		}
	}
}
int main(){
	FILE * pFile;
	pFile=fopen("alee.in","r");
	fscanf(pFile,"%d%d",&N,&M);
	for(i=1;i<=M;i++){
		fscanf(pFile,"%d%d",&x,&y);
		mat[x][y]=-1;
	}
	fscanf(pFile,"%d%d%d%d",&x1,&y1,&x2,&y2);
	mat[x1][y1]=1;
	Lee();
	pFile=fopen("alee.out","w");
	fprintf(pFile,"%d",mat[x2][y2]);
	return 0;
}

Sa ma impusti daca inteleg ce face for( j=m; j <= u; ++j ) ... De aici cred ca vine si ineficienta

void Lee()
{
	 int p, u, d;
	 	c[1][1]=x1;c[1][2]=y1;
	 	for( p=1,u=1;p<=u; ++p)
	  {
		   x=c[p][1];
				  y=c[p][2];
		 		for(d=0;d<4; ++d)
		  {
				 xnou=x+di[d];
				 ynou=y+dj[d];
							if(OK(xnou,ynou))
				{
					   mat[xnou][ynou]=p+1;
									  c[++u][1]=xnou;
						c[u][2]=ynou;
					   				if(xnou==x2 && ynou==y2)
											  return;
				  }
		   			}
			  }
	}

secretalex92, on 20th August 2011, 15:12, said:

Deci am folosit acel for pentru ca daca luam elementele din coada dupa pasul p atunci cand le dadeam valoarea p+1 cele de exemplu care trebuiau sa aiba valoarea 3 aveau 4,5......
For-ul acela ia toate elementele care trebuie sa aiba o anumita valoare
Si era:

m=u;
		for(j=p;j<=m;j++)

Si poate ca e un pic cam ineficient
Ma rog am rezolvat problema.Merge asa:

void Lee(){
	c[1][1]=x1;c[1][2]=y1;
	for(p=1,u=1;p<=u;p++){
		x=c[p][1];
		y=c[p][2];
		for(d=0;d<4;d++){
			xnou=x+di[d];
			ynou=y+dj[d];
			if(OK(xnou,ynou)){
				mat[xnou][ynou]=mat[x][y]+1;
				c[++u][1]=xnou;
				c[u][2]=ynou;
				if(xnou==x2 && ynou==y2){
					return;
				}
			}
		}
	}
}

Edited by Mitza444, 21 August 2011 - 09:19.

Imi poate spune cineva de ce imi da 0 0 0??Problema este insule de la OJI 2009,m-am tot uitat peste cod,dar nu-mi dau seama de ce imi da tot 0 0 0.(am facut numai determinarea numarului de insule)

#include<cstdio>
using namespace std;
int mat[101][101],n,m;
const int dx[] = { -1, 0, 1, 0 },dy[] = { 0, 1, 0, -1 };
void fill(int x,int y,int z){
	int xnou,ynou,i;
	for(i=0;i<4;i++){
		xnou=x+dx[i];
		ynou=y+dy[i];
		if( xnou < 1 || ynou < 1 || xnou > n || ynou > m || !mat[xnou][ynou])
			continue;
		mat[xnou][ynou]=0;
		fill(xnou,ynou,z);
	}
}
int main(){
	int i,j,R=0,G=0,B=0;
	FILE * pFile;
	pFile=fopen("insule.in","r");
	fscanf(pFile,"%d%d",&n,&m);
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			fscanf(pFile,"%d",&mat[i][j]);
		}
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			if(mat[i][j]==1){R++;fill(i,j,1);}
			if(mat[i][j]==2){G++;fill(i,j,2);}
			if(mat[i][j]==3){B++;fill(i,j,3);}
		}
	}
	pFile=fopen("insule.out","w");
	fprintf(pFile,"%d %d %d ",R,G,;
	return 0;
}

Edited by Mitza444, 13 September 2011 - 14:42.

Am rezolvat!!!Problema era la citire ca numerele nu avea spatiu intre ele si atunci trebuiau citite caracter cu caracter

Dar am o intrebare cum pot face determinarea podului??
Normal ar trebui sa iau toate zonele de apa care sunt vecine cu R si sa fac de acolo Lee pana in toate zonele cu apa care sunt vecine cu G si asta e cam complicat.

Edited by Mitza444, 13 September 2011 - 16:17.