824 Insule

[•DITzoneC]

Aici puteţi discuta despre problema Insule.

[•DraStiK]

Autorul trecut la aceasta problema este trecut: "Emanuele Cherchez".

Ar trebui modificat.

[•pauldb]

Am modificat.

[•BalcauIonut]

Am luat 94 pct la testul 7 nu face marimea podului bine..in rest totu e ok..ce e asa special cu testu ala?

[•BalcauIonut]

Gata am rezolvat..aveam un m in loc de n..cum valorile erau apropiate de obicei mergea dar in testu 7 nu

[•Mitza444]

Ma puteti ajuta si pe mine la rezolvarea acestei probleme??
Am determinat numar de insule cu flood fill,dar nu stiu cum sa determin podul...
Stiu ca se face cu Lee luand punctele care au vecin o tara R si facand Lee pana la o tara G,dar nu stiu cum sa fac asta(sa folosesc o  noua matrice sau cum??) ...
Aici e determinarea insulelor:

Cod:

#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;
		if(mat[xnou][ynou]==z){mat[xnou][ynou]=0;
		fill(xnou,ynou,z);}
	}
}
int main(){
	int i,j,R=0,G=0,B=0;
	char c;
	FILE * pFile;
	pFile=fopen("insule.in","r");
	fscanf(pFile,"%d%d\n",&n,&m);
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			fscanf(pFile,"%c",&c);
			mat[i][j]=c-'0';
		}
		fprintf(pFile,"\n");
	}
	pFile=fopen("insule.out","w");
	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);}
		}
		fprintf(pFile,"\n");
	}
	pFile=fopen("insule.out","w");
	fprintf(pFile,"%d %d %d\n",R,G,B);
	return 0;
}

[•PlayLikeNeverB4]

Da, folosesti o matrice noua pe care o initializezi cu valori mari, iar punctele vecine tarii 1 cu valoarea 1 (podul are deja lungimea 1).

[•Mitza444]

Am incercat sa rezolv problema folosind o noua matrice,dar nu stiu de ce  imi da o eroare dupa ce compilez ceva cu  return code -1073....
Ma puteti ajuta??

Cod:

#include<cstdio>
using namespace std;
int mat[101][101],n,m,M[101][101],min=99999;
const int dx[] = { -1, 0, 1, 0 },dy[] = { 0, 1, 0, -1 };
void Lee(int x, int y,int pod[101][101]){
		int xnou,ynou,p,u,c[101][2],xx,yy,d;
		pod[x][y]=1;
		c[1][0]=x;c[1][1]=y;
		for(p=0,u=0;p<=u;p++){
			xx=c[p][0];yy=c[p][1];
			for(d=0;d<4;d++){
				xnou=xx+dx[d];
				ynou=yy+dy[d];
				if(xnou>=1 && ynou>=1 && xnou<=n && ynou<=m && pod[xnou][ynou]==2){
					if(pod[xx][yy]<min)min=pod[xx][yy];
				}
				if(xnou>=1 && ynou>=1 && xnou<=n && ynou<=m && !pod[xnou][ynou]){
					pod[xnou][ynou]=pod[xx][yy]+1;
					c[++u][0]=xnou;
					c[u][1]=ynou;
				}
			}
		}
}
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 && !M[xnou][ynou]){
			Lee(xnou,ynou,M);}
		if( xnou < 1 || ynou < 1 || xnou > n || ynou > m || !mat[xnou][ynou])
			continue;
		if(mat[xnou][ynou]==z){mat[xnou][ynou]=0;
		fill(xnou,ynou,z);}
	}
}
int main(){
	int i,j,R=0,G=0,B=0;
	char c;
	FILE * pFile;
	pFile=fopen("insule.in","r");
	fscanf(pFile,"%d%d\n",&n,&m);
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			fscanf(pFile,"%c",&c);
			mat[i][j]=c-'0';
			M[i][j]=mat[i][j];
		}
		fprintf(pFile,"\n");
	}
	pFile=fopen("insule.out","w");
	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 %d\n",R,G,B,min);
	return 0;
}

[•PlayLikeNeverB4]

Iti lipseste fisierul de intrare?

[•SpiderMan]

@Mitza444, pe compilatoarele noi, faza cu fprintf(pFile, "\n") nu prea merge, foloseste cand scanezi un caracter (in cazul asta) fscanf (pFile, " %c ", &c) (vezi spatiile in interiorul " "), aia inseamna ca daca vede spatii dupa sau inainte de acel carater, nu le baga in seama. Deci stergi linia cu fprintf(pFile,"\n") si in loc de fscanf(pFile,"%c",&c) pui fscanf(pFile," %c ",&c) (sau fscanf(pFile," %c",&c) (fara spatiu dupa c, in cazul asta e acelasi lucru, dar foloseste-o pe prima)). Acum, daca faci asa pe campion (ca IA nu merge) o sa ai 40 puncte, datorita faptului ca podul e determinat gresit. Acum, remediing problema asta, vezi ca min e tot timpul 99999, nu stiu exact ce-ai facut tu pe acolo, dar te descurci. Daca ai nevoie si de ajutor aici, sa-mi dai niste detalii cum ai facut, poate te pot ajuta.

[•Mitza444]

Da nu imi iese podul nici cum tot 99999 imi da si nu stiu de ce.Deci eu m-am gandit asa sa fac un fill care determina numarul de insule si in paralel fac un Lee care imi determina lungimea podului.Pentru Lee am facut o functie care este apelata numai cand lanag gasesc o zona de apa care are vecin o tara R.Cand gasesc asta apelez functia care face Lee prin toata matricea si cand gaseste o zona de apa care are vecin o tara G. Daca lungimea pana acolo e mai mica decat min atunci min are lungimea respectiva.Daca poti,uitate un pic pe cod ,ca eu chiar nu-mi dau seama ce nu merge
Mersi:D

Cod:

#include<cstdio>
using namespace std;
int mat[101][101],n,m,M[101][101],min=99999;
const int dx[] = { -1, 0, 1, 0 },dy[] = { 0, 1, 0, -1 };
void Lee(int x, int y,int pod[101][101]){
		int xnou,ynou,p,u,c[101][2],xx,yy,d;
		pod[x][y]=1;
		c[1][0]=x;c[1][1]=y;
		for(p=0,u=0;p<=u;p++){
			xx=c[p][0];yy=c[p][1];
			for(d=0;d<4;d++){
				xnou=xx+dx[d];
				ynou=yy+dy[d];
				if(xnou>=1 && ynou>=1 && xnou<=n && ynou<=m && pod[xnou][ynou]==2){
					if(pod[xx][yy]<min)min=pod[xx][yy];
				}
				if(xnou>=1 && ynou>=1 && xnou<=n && ynou<=m && !pod[xnou][ynou]){
					pod[xnou][ynou]=pod[xx][yy]+1;
					c[++u][0]=xnou;
					c[u][1]=ynou;
				}
			}
		}
}
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 && !M[xnou][ynou] && z==1){
			Lee(xnou,ynou,M);}
		if( xnou < 1 || ynou < 1 || xnou > n || ynou > m || !mat[xnou][ynou])
			continue;
		if(mat[xnou][ynou]==z){mat[xnou][ynou]=0;
		fill(xnou,ynou,z);}
	}
}
int main(){
	int i,j,R=0,G=0,B=0;
	char c;
	FILE * pFile;
	pFile=fopen("insule.in","r");
	fscanf(pFile,"%d%d\n",&n,&m);
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			fscanf(pFile,"%c",&c);
			mat[i][j]=c-'0';
			M[i][j]=mat[i][j];
		}
		fscanf(pFile,"%c",&c);
	}
	pFile=fopen("insule.out","w");
	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 %d\n",R,G,B,min);
	return 0;
}

[•PlayLikeNeverB4]

Pai tu folosesti matricea M ca sa memorezi insulele si o folosesti si ca sa memorezi distantele. Pentru distante iti trebuie alta matrice. In loc de "c[1][0]=x;c[1][1]=y;" pune "c[0][0]=x;c[0][1]=y;" pentru ca incepi cu p de la 0. Aa si nu e destula o coada de 101 elemente, pune 10001.

In locul tau eu asa face asa: in loc sa faci de mai multe ori Lee-ul ala, mai bine parcurgi toata matricea si introduci in coada toate celulele vecine cu o insula dintre cele doua (depinde cu care vrei sa incepi), le initializezi cu 1 si rulezi Lee-ul.

[•Mitza444]

Mersi n-am vazut faza cu coada ca eu o pneam de la 1 si la primul pas se termina for-ul deaia imi tot dadea 9999.
George eu folosesc matricea pod din functia  din functia Lee care ia de fiecare data valoarile din matricea M care e o copie a matricei mat,pe care no schimb.
Dar inca mai am o problema ca nu stiu de ce nu merge calumea Lee-ul.Drumul care il calculeaza nu e corect ,dar nu stiu de ce.

[•PlayLikeNeverB4]

Nu merge pentru ca acea matrice pod la tine retine unde e insula de tip 1, 2 sau 3, iar tu o folosesti ca sa retii lungimea podului.
Aa, si inca o chestie. Matricea este transmisa prin referinta, deci valorile pe care le modifici in interiorul functiei vor ramane asa si in afara functiei. Din fericire, aici nu conteaza.
Nu vrei tu sa faci cum ti-am zis eu? E mult mai simplu.

[•Mitza444]

Pai tu zici ca atunci cand fac fill-ul daca gasesc o zona cu apa cu vecin tara R il retin intr-o coada.Bun si dupa ce determin toate punctele nu trebuie sa iau fiecare punct si pe o matrice noua ca si cea initiala pe care o citesc sa fac Lee(matricea trebuie sa fie tot timpul cea initiala ca sa pot pune lungimea drumului pe ea adica primul punct o sa aiba val 1 dupa aceea urmatoarele vecine 2 si tot asa pana dau de o zona cu vecin tara G)??Deci nu e acelasi lucru cu ce am facut eu numai ca mai folosesc inca o coada pt a retine punctele si dupaia fac Lee?

[•PlayLikeNeverB4]

Deci fii atent: Ai matricea M cu semnificatia M[i][j] = tara din care face parte celula (i,j).
Vei mai avea nevoie de o matrice D cu semnificatia D[i][j] = distanta minima de la o celula apartinand tarii 1 pana la celula (i,j).
Din cate imi dau seama, tu folosesti celula M pentru ambele informatii.
P.S.: Daca mai ai nelamuriri trimite-mi PM ca sa nu umplem tot forumul.

[•VisuianMihai]

un pod poate avea CURBE?? adica poate fi pe orizontala si in acelasi timp si pe verticala in matrice?

[•PlayLikeNeverB4]

Nu-s chiar curbe, dar unghiuri de 90 de grade da.

[•tsuby]

Cum se face mai exact lee-ul la problema asta? Am luat o a doua matrice in care imi marchez ce apartine de tara 3 ca obstacol. Treaba evidenta e ca trebuie sa-mi marchez si insulele care nu au vecini ca obstacole.
Inafara de asta, trebuie sa pornesc leeul de la fiecare pozitie care are in compozitie o grupare de 1.

[•balanta7]

dc stau si astept si nu mi se verifica problema???

[•paulborza]

As vrea si eu o implementare in pascal a algoritmului fill. Ma poate ajuta cineva?

[•anaking1994]

Zice ca nu imi merge niciun test. Am luat testele de pe olimpiada.info si cateva imi merg,mai ales prima cerinta. Unde gresesc? Multumesc anticipat !

Cod:

#include<stdio.h>
int n,m,a[100][100],s[100][100],x[5]={0,1,0,-1,0},y[5]={0,0,-1,0,1},min=1000;
FILE *f=fopen("insule.in","r");
FILE *g=fopen("insule.out","w");
void citire()
{
	int i,j;
	fscanf(f,"%d",&n);
	fscanf(f,"%d\n",&m);
	for(i=0;i<n;i++)
	{
		for(j=0;j<m;j++)
		{
			fscanf(f,"%c",&a[i][j]);
			s[i][j]=a[i][j];
			a[i][j]=a[i][j]-48;
			s[i][j]=s[i][j]-48;
		}
		fprintf(f,"\n");
	}
	fclose(f);
}
void insule(int i,int j,int k)
{
	int ii,jj,l;
	for(l=1;l<=4;l++)
	{
		ii=i+x[l];
		jj=j+y[l];
		if(ii>=0 && ii<n && jj>=0 && jj<m )
			if(a[ii][jj]==k)
			{
				a[ii][jj]=0;
				insule(ii,jj,k);
			}
	}
}
void traseu(int i,int j,int pas)
{
	int ii,jj,k;
	for(k=1;k<4;k++)
	{
		ii=i+x[k];
		jj=j+y[k];
		if(ii<n && ii>=0 && jj<m && jj>=0)
			if(s[ii][jj]!=-1 && s[ii][jj]!=-3)
				if(s[ii][jj]==-2)
				{
					if(s[i][j]<min && s[i][j]>0)
					{
						min=s[i][j];
					}
					break;
				}
				else
					if(s[ii][jj]>pas || s[ii][jj]==0)
					{
						s[ii][jj]=pas;
						traseu(ii,jj,pas+1);
					}
	}
}
int main()
{
	citire();
	int i,j,nr=0,ng=0,nb=0;
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
		{
			if(a[i][j]==1)
			{
				a[i][j]=0;
				insule(i,j,1);
				nr++;
			}
			else
				if(a[i][j]==2)
				{
					ng++;
					a[i][j]=0;
					insule(i,j,2);
				}
				else
					if(a[i][j]==3)
					{
						nb++;
						a[i][j]=0;
						insule(i,j,3);
					}
		}
	fprintf(g,"%d %d %d ",nr,ng,nb);
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
		{
			if(s[i][j]==3)
				s[i][j]=-3;
			if(s[i][j]==1)
				s[i][j]=-1;
			if(s[i][j]==2)
				s[i][j]=-2;
		}
	
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
			if(s[i][j]==-1)
				traseu(i,j,1);
	fprintf(g,"%d",min);
	fclose(g);
}

Editat de moderator: Foloseste tagul code pentru afisa sursele.

[•superman_01]

imi spuneti va rog ce implementare sa fac ca sa iau 100?iau TLE pe tesul 6 si 10..pe testele de la oji imi merge perfect...

[•NicuCJ]

Faci un algoritm de fill care sa-ti numere insulele cu 1, cu 2, respectiv cu 3. Bineinteles, tre sa schimbi valoarea unui 1, 2 sau 3 cand treci prin el pentru a nu trece din nou. Eu le-am inlocuit cu 100001, 100002 si 100003.

Dupa aceea, faci un lee de la fiecare punct din matrice cu 1, care sa treaca doar prin 0-urile din matrice. Apoi iei fiecare punct cu 2 din matrice si verifici daca elementele din sus, stanga, dreapta sau jos sunt 0. Daca unul e 0, actualizezi minimul (daca e cazul), cu ce ai in matricea in care ai facut lee-ul.

Succes!

[•superman_01]

mersi de ajutor