infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Adrian Diaconu din Mai 26, 2009, 21:50:11


Titlul: 824 Insule
Scris de: Adrian Diaconu din Mai 26, 2009, 21:50:11
Aici puteţi discuta despre problema Insule (http://infoarena.ro/problema/insule).

Titlul: Răspuns: 824 Insule
Scris de: Dragos Oprica din Mai 27, 2009, 13:16:18
Autorul trecut la aceasta problema este trecut: "Emanuele Cherchez".

Ar trebui modificat. :ok:

Titlul: Răspuns: 824 Insule
Scris de: Paul-Dan Baltescu din Mai 27, 2009, 13:37:48
Am modificat.

Titlul: Răspuns: 824 Insule
Scris de: FMI-Balcau Ionut din Februarie 25, 2010, 20:27:53
Am luat 94 pct la testul 7 nu face marimea podului bine..in rest totu e ok..ce e asa special cu testu ala?

Titlul: Răspuns: 824 Insule
Scris de: FMI-Balcau Ionut din Februarie 25, 2010, 21:34:24
Gata am rezolvat..aveam un m in loc de n..cum valorile erau apropiate de obicei mergea dar in testu 7 nu :D

Titlul: Răspuns: 824 Insule
Scris de: Vidrean Mihai din Septembrie 19, 2011, 11:56:00
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??) :eyebrow:...
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;
}

Titlul: Răspuns: 824 Insule
Scris de: George Marcus din Septembrie 19, 2011, 13:47:02
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).

Titlul: Răspuns: 824 Insule
Scris de: Vidrean Mihai din Septembrie 20, 2011, 14:38:30
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;
}


Titlul: Răspuns: 824 Insule
Scris de: George Marcus din Septembrie 20, 2011, 14:57:02
Iti lipseste fisierul de intrare? :)

Titlul: Răspuns: 824 Insule
Scris de: Simoiu Robert din Septembrie 20, 2011, 16:02:44
@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.

Titlul: Răspuns: 824 Insule
Scris de: Vidrean Mihai din Septembrie 20, 2011, 19:03:31
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 #-o
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;
}

Titlul: Răspuns: 824 Insule
Scris de: George Marcus din Septembrie 20, 2011, 20:19:52
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.

Titlul: Răspuns: 824 Insule
Scris de: Vidrean Mihai din Septembrie 20, 2011, 21:00:13
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. ](*,)

Titlul: Răspuns: 824 Insule
Scris de: George Marcus din Septembrie 20, 2011, 21:52:54
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.

Titlul: Răspuns: 824 Insule
Scris de: Vidrean Mihai din Septembrie 22, 2011, 14:36:39
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?

Titlul: Răspuns: 824 Insule
Scris de: George Marcus din Septembrie 22, 2011, 15:01:55
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.

Titlul: Răspuns: 824 Insule
Scris de: Mihai Visuian din Septembrie 23, 2011, 15:10:41
un pod poate avea CURBE?? adica poate fi pe orizontala si in acelasi timp si pe verticala in matrice? :horsy:

Titlul: Răspuns: 824 Insule
Scris de: George Marcus din Septembrie 23, 2011, 15:49:33
Nu-s chiar curbe, dar unghiuri de 90 de grade da.

Titlul: Răspuns: 824 Insule
Scris de: Razvan Idomir din Februarie 11, 2012, 11:43:46
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.

Titlul: Răspuns: 824 Insule
Scris de: oarna alexandru din Februarie 27, 2012, 13:47:07
dc stau si astept si nu mi se verifica problema??? :angry:

Titlul: Răspuns: 824 Insule
Scris de: Borza Paul din Martie 01, 2012, 19:46:36
As vrea si eu o implementare in pascal a algoritmului fill. Ma poate ajuta cineva? :)

Titlul: Răspuns: 824 Insule
Scris de: Certezeanu Razvan din Martie 06, 2012, 11:49:10
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.

Titlul: Răspuns: 824 Insule
Scris de: Avramescu Cristian din Decembrie 16, 2012, 19:04:22
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...

Titlul: Răspuns: 824 Insule
Scris de: Nicu B. din Decembrie 17, 2012, 15:06:46
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!

Titlul: Răspuns: 824 Insule
Scris de: Avramescu Cristian din Decembrie 19, 2012, 22:13:53
mersi de ajutor :)

Titlul: Răspuns: 824 Insule
Scris de: Avramescu Cristian din Decembrie 20, 2012, 15:47:35
am facut cum zici...si tot iau TLE pe alea 2 si nu inteleg de ce ](*,)....

Titlul: Răspuns: 824 Insule
Scris de: Cosmin Ionut din Ianuarie 07, 2013, 12:53:31
Podul nu poate fi in zigzag , nu ?

Titlul: Răspuns: 824 Insule
Scris de: Andrei Iulian din Februarie 06, 2013, 21:27:13
Chiar nu-mi dau seama unde cicleaza codul.  ](*,) Poate va uitati putin si ma ajutati si pe mine :D

#include<iostream>
#include<fstream>
using namespace std;

ifstream f ("insule.in");
ofstream gin ("insule.out");

int a[100][100],i,j,n,m,b[100][100];
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};

struct punct {int x,y;} c[10000];

void fill (int x,int y,int k)
{if (a
  • [y]==k) {a
  • [y]=k*-1;
fill(x-1,y,k);
fill(x,y+1,k);
fill(x+1,y,k);
fill(x,y-1,k);}}

int lee(int x0,int y0)
{int k,u,p,xc,yc,xv,yv;
   for (i=0;i<=n+1;i++)
   for (j=0;j<=m+1;j++)
      b[j]=a[j];
c[1].x=x0; c[1].y=y0;
u=p=1;
while (p<=u)
{xc=c[p].x; yc=c[p].y;
   for (k=0;k<4;k++)
{xv=xc+dx[k];
yv=yc+dy[k];
if (b[xv][yv] == -2) return b[xc][yc];
else
   if (b[xv][yv] == 0)
   {b[xv][yv]=b[xc][yc]+1;
   u++; c.x=xv;  c.y=yv;}
else
   if (b[xv][yv]>0 && b[xv][yv]>b[xc][yc]+1)
   {b[xv][yv]=b[xc][yc]+1;
   u++; c.x=xv; c.y=yv;}
} }
p++;}

int main()
{   char x;
int q,min=10000;
   int r=0,g=0,b=0;
    f>>n>>m;
//bordare matrice cu -4;
for (i=0;i<=n+1;i++)
   a
  • =a[m+1]=-4;
for (j=0;j<=m+1;j++)
   a[0][j]=a[n+1][j]=-4;
//citire in matrice;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
{f>>x; a[j]=x-'0';}
//verificare numar insule;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
{if (a[j]==1) {r++; fill(i,j,1);}
if (a[j]==2) {g++; fill(i,j,2);}
if (a[j]==3) {b++; fill(i,j,3);}}
//lungime min pod;
for (i=1;i<=n;i++)
   for (j=1;j<=m;j++)
   {q=lee(i,j);
   if (q<min) min=q;}

gin<<r<<" "<<g<<" "<<b<<" "<<min;
f.close(); gin.close();
return 0;}

Titlul: Răspuns: 824 Insule
Scris de: Bogdan Pop din Iulie 10, 2013, 12:44:36
nu inteleg, imi da exact ca in exemplu si iau 0,rezolvarea cred ca este buna ...am trimis si pe evaluatorul de pe campion.edu.ro,si acolo la exemplu 0 puncte,chiar daca imi da exact la fel. Uitati-va va rog peste cod si spuneti-mi ce sa fac:

Citat
#include <cstdio>
#define MAX 101
using namespace std;

int x[MAX][MAX], a[MAX][MAX];
int n,m,size,max(-9999),R,G,B;
int d1[] = { -1, 0, 1, 0};
int d2[] = { 0, 1, 0, -1 };
int minim(999999);

bool ok(int i, int j)
{
    if ( a[j] != 0 )
    return false;
    if ( i < 1 || j < 1 || i > m || j > m)
    return false;
    return true;
}

void lee()
{
    int k(4); int v1,v2;bool modif = true;
    while ( modif )
    {
        modif = false;
    for ( int i = 1; i <= n; i++)
        for ( int j = 1; j <= m; j++ )
        if ( a[j] == k)
        {
            for ( int d = 0; d < 4; d++ )
            {
                v1 = i + d1[d];
                v2 = j + d2[d];
                if ( ok(v1,v2) )
                {
                a[v1][v2] = k+1;
                modif = true;
                }
            }

        }
         k++;
    }
}

struct pozitie{
    int linie;
    int coloana;
    };

void fill(int i,int j,int k)
{
    if ( x[j] == 1)
    {
        x[j]=k;
        size++;
        if ( x[i-1][j] == 1) fill(i-1,j,k);
        if ( x[i+1][j] == 1) fill(i+1,j,k);
        if ( x[j-1] == 1) fill(i,j-1,k);
        if ( x[j+1] == 1) fill(i,j+1,k);

    }
    if ( x[j] == 2)
    {
        x[j]=k;
        size++;
        if ( x[i-1][j] == 2) fill(i-1,j,k);
        if ( x[i+1][j] == 2) fill(i+1,j,k);
        if ( x[j-1] == 2) fill(i,j-1,k);
        if ( x[j+1] == 2) fill(i,j+1,k);

    }
    if ( x[j] == 3)
    {
        x[j]=k;
        size++;
        if ( x[i-1][j] == 3) fill(i-1,j,k);
        if ( x[i+1][j] == 3) fill(i+1,j,k);
        if ( x[j-1] == 3) fill(i,j-1,k);
        if ( x[j+1] == 3) fill(i,j+1,k);

    }
}



int main()
{
    char c;int d;
    pozitie p1[100];
    pozitie p2[100];
    FILE * pFile;
    pFile = fopen("insule.in", "r");
    fscanf(pFile,"%d%d\n", &n,&m);
    for ( int i = 1; i <= n ; i++ )
    {
        for ( int j = 1 ; j <= m; j++ )
        {
            fscanf(pFile,"%c",&c);
            x[j] = c - '0';
            a[j] = c - '0';
        }
        fprintf(pFile,"\n");
    }
    int k = 3;
    for ( int i = 1; i <= n; i++ )
        for ( int j = 1; j <= m; j++ )
        if ( x[j] == 1 || x[j] == 2 || x[j] == 3 )
        {
            k++;
            if ( x[j] == 1)
            R++;
            if ( x[j] == 2)
            G++;
            if ( x[j] == 3)
            B++;
            size = 0;
            fill(i,j,k );
            if ( size > max )
            max = size;
        }
        int o = 0;
        int p = 0;
        int j1,j2;
    for ( int i = 1; i <= n; i++ )
        for ( int j = 1; j <= m; j++ )
        {
            if ( a[j] == 0 )
            {
                if ( a[i-1][j] == 1 || a[i+1][j] == 1 || a[j-1] == 1 || a[j+1] == 1)
                {
                    p1
  • .linie = i;
                    p1
  • .coloana = j;
                    j1 = i;
                    j2 = j;
                    a[j1][j2] = 4;
                    o++;
                }
                if ( a[i-1][j] == 2 || a[i+1][j] == 2 || a[j-1] == 2 || a[j+1] == 2)
                {
                    p2[p].linie = i;
                    p2[p].coloana = j;
                    p++;
                }
            }
        }
    lee();
    int f,g;
    for ( int j = 0; j < p ; j++ )
        {
            f = p2[j].linie;
            g = p2[j].coloana;
            if ( a[f][g] < minim && a[f][g] != 0)
            minim = a[f][g];
        }
    minim -= 3;
    pFile = fopen("insule.out", "w");
    fprintf(pFile, "%i %i %i %i" ,R,G,B,minim);

    return 0;
}

Titlul: Răspuns: 824 Insule
Scris de: George Marcus din Iulie 10, 2013, 13:16:41
Cod:
fprintf(pFile,"\n");
?

Titlul: Răspuns: 824 Insule
Scris de: Bogdan Pop din Iulie 10, 2013, 13:45:15
Fara acea linie nu citeste matricea cum trebuie.daca nu o puneam,ramanea la prima linie citirea elementelor din matrice.

Titlul: Răspuns: 824 Insule
Scris de: George Marcus din Iulie 10, 2013, 19:36:06
Pune
Cod:
fscanf(pFile,"\n");

Ce sens are sa scrii intr-un fisier din care citesti? :)

Titlul: Răspuns: 824 Insule
Scris de: Dinca Liviu din August 07, 2014, 17:52:55
Va rog frumos sa ma ajutati!
Nu imi dau seama cum sa adaug toate zonele vecine in coada.Eu le-am luat pe toate si am facut Lee-ul la fiecare-n parte.Iau doar 70 de puncte.
Pe ultimele 3 teste iau TLE.
Ma incurc mereu.Are cineva o idee cum sa implementez?

Titlul: Răspuns: 824 Insule
Scris de: Valeriu Motroi din August 15, 2014, 09:58:11
Daca te referi la aflarea numarului de insule, poti sa folosesti Flood fill http://en.m.wikipedia.org/wiki/Flood_fill

Titlul: Răspuns: 824 Insule
Scris de: Dinca Liviu din August 21, 2014, 11:30:16
Aflarea numarului de insule a fost simpla...punctul 2 ma intereseaza.Am facut lee-ul pt fiecare vecin al primei tari si iau 70 de puncte(ultimele 3 TLE).Eu vreau sa adaug toti vecinii in coada si sa fac o singura data lee-ul.Dar nu imi dau seama cum...  :-k

Titlul: Răspuns: 824 Insule
Scris de: Dinca Liviu din August 21, 2014, 11:31:20
Aflarea numarului de insule a fost simpla...punctul 2 ma intereseaza.Am facut lee-ul pt fiecare vecin al primei tari si iau 70 de puncte(ultimele 3 TLE).Eu vreau sa adaug toti vecinii in coada si sa fac o singura data lee-ul.Dar nu imi dau seama cum...  :-k

Titlul: Răspuns: 824 Insule
Scris de: George Marcus din August 21, 2014, 16:05:21
Faci exact cum ai spus. Bagi totul in coada, setezi distanta pentru acele puncte la 0 si ii dai drumul. Nu e nimic special. Explica ce nu intelegi.

Titlul: Răspuns: 824 Insule
Scris de: Dragulin Silviu din Septembrie 28, 2014, 14:18:42
buna
nu stiu cum sa citesc matricea aia fara spati intre elemente  :fighting:  :'(
ma poate ajuta cineva ? :D

Titlul: Răspuns: 824 Insule
Scris de: George Marcus din Septembrie 28, 2014, 21:27:20
Citesti N siruri de caractere.

Titlul: Răspuns: 824 Insule
Scris de: Dragulin Silviu din Septembrie 28, 2014, 21:56:45
am facut problema ,am citit pe o matrice de tip char apoi am am trecut toate datele pe o matrice normala,pe datele de pe problema
imi da 4 2 3 4;dar cand am trimis problema am luat 0 puncte  :'( ,de ce? te poti uita putin peste programul meu ? multumesc  anticipat ! :)

#include <fstream>
#include <iomanip>
using namespace std;
ifstream x("insule.in");
ofstream y("insule.out");
struct lee
 {
     int lin,col;
 };
int dl[]={-1,0,1,0};//deplasarea pe linie
int dc[]={0,1,0,-1};//deplasarea pe coloana

char a[101][101];/*arhipelagul  cu insule,este de tip char
pt ca datele din matrice pe linie nu sunt separate prin spatiu*/

int i,j,m,n,prim,ultim,k,b[101][101],insule[4],limita;/*am facut
o copiiea arhipelaguluide tip int pentru ca pe char
nu pot prelucra datele,iar limitele le voi folosi in mai jos
in conditia de continuitate a algoritmului lui lee */

int pod,pod_min; // un pod si podul de lungime minima

lee c[10000],v,p,start; //coada,vecinul,pozitia curenta si startul


void citesc()
 {
     x>>n>>m;
     for(i=1;i<=n;i++)
       for(j=1;j<=m;j++)
         {
             x>>a[j];
             b[j]=a[j]-48;
         }

 }
void scriu()
 {

     for(i=1;i<=n;i++)
      {
           for(j=1;j<=m;j++)
             y<<setw(4)<<b[j];
           y<<'\n';

      }
     y<<"\n\n\n";
 }
void lee()
 {
     prim=ultim=0;
     c[0]=start;
     while(prim<=ultim)
      {
          p=c[prim];
          prim++;
          for(k=0;k<4;k++)
           {
               v.lin=p.lin+dl[k];
               v.col=p.col+dc[k];
               //if(b[v.lin][v.col]!=0 && b[v.lin][v.col]<100 )
               if(b[v.lin][v.col]==limita )
                {
                    b[v.lin][v.col]=b[v.lin][v.col]+100;
                    ultim++;
                    c[ultim]=v;

                }

           }

      }

 }
void p1()
 {
     for(i=1;i<=n;i++)
      for(j=1;j<=m;j++)
         {
             if(b[j]!=0 && b[j]<100)
               {
                   insule[b[j]]++;
                   start.lin=i;
                   start.col=j;
                   limita=b[j];
                   //y<<limita<<' ';
                   b[j]=b[j]+100;
                   lee();
               }
         }

 }
void lee2()/*am modificat potin lee-ul astfel incat de la start sa
sa ia directiile pe rand si la fiecare directie sa mearga in liniie
dreapnta pana cand gaseste sau nu gaseste ceva pt a fi numit pod;
daca incepe din 1 apoi parcrurgem numai zero-uri pana la un 2,il
consideram pod,daca il  consideram pod ne interesam daca este de
lungime minima... :)  */

 {
     prim=ultim=0;
     c[0]=start;
     for(k=0;k<4;k++)
      {
          v.lin=start.lin+dl[k];
          v.col=start.col+dc[k];
          while(a[v.lin][v.col]==0)
           {
               pod++;
               v.lin+=dl[k];
               v.col+=dc[k];
           }
          if(a[v.lin][v.col]==2 && pod<pod_min)
             pod_min=pod;
           pod=0;
      }

 }
void p2()
 {
     for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
       {
           if(a[j]==1)
            {
                start.lin=i;
                start.col=j;
                lee2();
            }

       }
      y<<pod_min;
 }

int main()
{
    citesc();
    //scriu();
    p1();
    //scriu();
    for(i=1;i<=3;i++) y<<insule<<" ";
    if(m<n) pod_min=m-2;//vad care ar putea fi lungimea maxima a unui pod
        else pod_min=n-2;
    p2();


    return 0;
}

Titlul: Răspuns: 824 Insule
Scris de: Mihailescu Vlad Tiberiu din Noiembrie 01, 2014, 12:49:08
Imi explica si mie cineva de ce scrie N,M <= 100 si solutia mea ia 10 puncte pt a[102][102] , 88 puncte pe a[150][150], 70 puncte pe a[300][300] si 100 pentru a[256][256] ???? Si nu cumva o matrice de 256 pe 256 si o coada (cu 2 unsigned char-uri) depaseste 640 kbytes?

Titlul: Răspuns: 824 Insule
Scris de: Axinie Razvan din Ianuarie 07, 2015, 16:43:28
BAD POST.
L.E:
Cei care credeti ca algoritmul este corect dar totusi nu luati 100, declarati matricea mai mare.
Pentru 3 matrici 101x101 am luat 88p, iar pentru 3 matrici 110x110 am luat 100p.

Titlul: Răspuns: 824 Insule
Scris de: Tibi P din Iulie 16, 2015, 21:39:52
Am si eu o problema daca ma puteti ajuta:
sursa mea ia pe 9 teste 4 puncte cu eroarea "lungime minima gresita", un test fiind "OK" (total 46p ): http://www.infoarena.ro/job_detail/1462033?action=view-source

( am incercat sa iau si minimul de lungime a unui pod din subprogramul " podu'() ", ce face defapt si actualul subprogram din sursa de mai sus dar asa, ca chestie:
http://www.infoarena.ro/job_detail/1462036?action=view-source  si desigur, la fel: 46p ).

Nu pot sa mi dau seama unde ar fi problema, in principiu ar trebui sa fie bine, si pe actualul exemplu imi da bine.

Titlul: Răspuns: 824 Insule
Scris de: Alin Pisica din Ianuarie 05, 2016, 21:06:16
Pe 8/10 teste imi da "Lungimea minima gresita"... Putin ajutor se poate?
Cod:
#include <iostream>
#include <fstream>
#include <queue>
 
std::ifstream fin("insule.in");
std::ofstream fout("insule.out");
 
int n, m; //Linii, coloane
int Map[105][105]; //Matrice
std::queue < std::pair < int, int > > coada; //Coada
std::queue < std::pair < int, int > > pod; //CoadaPentruPod
const int di[4] = {1, -1, 0, 0}, //Deplasare pe linie
          dj[4] = {0, 0, 1, -1}; //Deplasare pe coloana
int tipInsula;
int insule[4], Lg = 999999;
 
void Read(){
    char c;
    fin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            fin >> c;
            Map[i][j] = c - '0';
        }
    }
}
 
bool OKinsula(int a, int b, int t){
    if(Map[a][b] == t && a >= 1 && b >= 1 && a <= n && b <= m)
        return true;
    return false;
}
 
bool OKapa(int a, int b){
    if(Map[a][b] == 0 && a >= 1 && b >= 1 && a <= n && b <= m)
        return true;
    return false;
}
 
bool apaInceputPod(int a, int b){
    if (Map[a][b] == 0 && (Map[a-1][b] == 1 || Map[a+1][b] == 1 || Map[a][b-1] == 1 || Map[a][b+1] == 1 || Map[a-1][b] == -1 || Map[a+1][b] == -1 || Map[a][b-1] == -1 || Map[a][b+1] == -1))
        return true;
    return false;
}
 
void numarInsule(){
    int i_curent, j_curent; //Pastrarea pozitiei curente
    int i_urmator, j_urmator; //Pastrarea pozitiei urmatoare
    while (!coada.empty()){
        i_curent = coada.front().first;
        j_curent = coada.front().second;
        coada.pop();
        for (int directie = 0; directie < 4; directie++){
            i_urmator = i_curent + di[directie];
            j_urmator = j_curent + dj[directie];
            if (OKinsula(i_urmator, j_urmator, tipInsula)){
                coada.push(std::make_pair(i_urmator, j_urmator));
                Map[i_urmator][j_urmator] *= -1;
            }
        }
    }
}
 
void verificaLungimea(){
    for (int a = 1; a <= n; a++){
        for (int b = 1; b <= n; b++){
            if (Map[a][b] > 0 && (Map[a-1][b] == -2 || Map[a+1][b] == -2 || Map[a][b-1] == -2 || Map[a][b+1] == -2)){
                if(Map[a][b] <= Lg){
                    Lg = Map[a][b];
                }
            }
        }
    }
}
 
void calculeazaLungimea(){
    int i_curent, j_curent; //Pastrarea pozitiei curente
    int i_urmator, j_urmator; //Pastrarea pozitiei urmatoare
    i_curent = pod.front().first;
    j_curent = pod.front().second;
    Map[i_curent][j_curent] = 1;
    while (!pod.empty()){
        i_curent = pod.front().first;
        j_curent = pod.front().second;
        pod.pop();
        for (int directie = 0; directie < 4; directie++){
            i_urmator = i_curent + di[directie];
            j_urmator = j_curent + dj[directie];
            if (OKapa(i_urmator, j_urmator)){
                pod.push(std::make_pair(i_urmator, j_urmator));
                Map[i_urmator][j_urmator] = Map[i_curent][j_curent] + 1;
            }
        }
    }
    verificaLungimea();
}
 
int main(int argc, char *argv[]){
    Read();
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (apaInceputPod(i, j)){
                pod.push(std::make_pair(i, j));
            }else if (Map[i][j] > 0 && i >= 1 && j >= 1 && i <= n && j <= m){
                tipInsula = Map[i][j];
                switch (Map[i][j]){
                    case 1:
                        insule[1]++;
                        break;
                    case 2:
                        insule[2]++;
                        break;
                    case 3:
                        insule[3]++;
                        break;
                    default:
                        break;
                };
                if(coada.empty())
                    Map[i][j] *= -1;
                coada.push(std::make_pair(i, j));
                numarInsule();
            }
        }
    }
    calculeazaLungimea();
    fout << insule[1] << " " << insule[2] << " " << insule[3] << " " << Lg;
    return 0;
}

Titlul: Răspuns: 824 Insule
Scris de: Samoilescu Sebastian din Decembrie 11, 2016, 19:24:59
Buna seara !Am si eu o nedumerire,pentru exemplul urmator ce ar trebui sa afiseze programul?
6 7
1 0 0 0 3 2 0
0 1 1 0 3 1 3
3 3 3 0 0 0 2
2 0 3 3 0 0 0
2 2 0 3 0 1 1
2 0 0 0 0 1 0
Multumesc!

Titlul: Răspuns: 824 Insule
Scris de: Alexandru Valeanu din Decembrie 11, 2016, 22:46:39
Mie imi da:
Cod:
4 3 3 1

Titlul: Răspuns: 824 Insule
Scris de: Maslinca Alecsandru Mihai din Februarie 13, 2017, 12:44:14
Nu stie cineva de ce primesc constant 0 puncte?
Cod:
#include <iostream>
#include <fstream>
using namespace std;

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


int dl[4]= {0,1,0,-1};
int dc[4]= {1,0,-1,0};
int v[250][250];
int x[4];
void Lee(int i,int j,int &mx,int n,int m)
{

    for (int di=0; di<4; di++)
    {
        int iu=i,ju=j,o=0;
        iu+=dl[di];
        ju+=dc[di];
        while (v[iu][ju]==0&&iu>-1&&ju>-1&&iu<n&&ju<m)
        {
            o++;
            iu+=dl[di];
            ju+=dc[di];
        }
        if (v[iu][ju]==2)
            if (o<mx&&o!=0)
                mx=o;
    }
}


int main()
{
    int n,m,a,mx=105;
    f>>n>>m;
    for (int i=0; i<n; i++)
    {
        f>>a;
        int j=0;
        while (a)
        {
            v[i][m-j-1]=a%10;
            a/=10;
            j++;
        }
    }
    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++)
        {
            if (v[i][j])
                if (v[i-1][j]!=v[i][j]&&v[i][j-1]!=v[i][j])
                    x[v[i][j]]++;
            if (v[i][j]==1)
                Lee(i,j,mx,n,m);
        }
    for (int i=1; i<4; i++)
        g<<x[i]<<' ';
    if (mx!=105)
    g<<mx;
    else
        g<<0;
    f.close();
    g.close();
    return 0;
}

Titlul: Răspuns: 824 Insule
Scris de: Nicolae Filat din Aprilie 02, 2018, 12:58:27
Nu esti corect, fraiere !!!  :evil: :evil: :evil: :evil: :evil: :evil: :evil: :evil:


Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines