Imprimă pagina - 1163 Tsunami

Titlul: 1163 Tsunami
Scris de: Savin Tiberiu din Mai 06, 2011, 14:45:59

Aici puteti discuta despre problema Tsunami (http://infoarena.ro/problema/tsunami).

[Multumiri lui Simoiu Robert (http://infoarena.ro/utilizator/spiderman) pentru ca a adaugat aceasta problema in arhiva]

Titlul: RÄƒspuns: 1163 Tsunami
Scris de: Vidrean Mihai din Ianuarie 20, 2012, 23:10:14

Nu stiu de ce iau killed by signal 11 ](*,) la testul 3 si 10.Va puteti uita putin peste sursa??Chiar nu imi dau seama ce am gresit.

Cod:

#include<cstdio>
using namespace std;
#define MAX 1002
int n,m,h,nr=0;
int mat[MAX][MAX];
bool q[MAX][MAX];
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
void fill(int x,int y){
	int xnou,ynou,d;
	q[x][y]=1;
	if(mat[x][y]){
		mat[x][y]=0;
		nr++;
	}
	for(d=0;d<4;d++){
		xnou=x+dx[d];
		ynou=y+dy[d];
		if((mat[xnou][ynou]<h)&& !q[xnou][ynou] && xnou>=1 && xnou<=n && ynou>=1 && ynou<=m)
			fill(xnou,ynou);
	}
}
int main(){
	freopen("tsunami.in","r",stdin);
	freopen("tsunami.out","w",stdout);
	int i,j;
	scanf("%d%d%d",&n,&m,&h);
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++)
			scanf("%d",&mat[i][j]);
	}
	fclose(stdin);
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			if(mat[i][j]==0 && !q[i][j])
				fill(i,j);
		}
	}
	printf("%d\n",nr);
	fclose(stdout);
	return 0;
}

Titlul: RÄƒspuns: 1163 Tsunami
Scris de: coman cosmin din Februarie 14, 2012, 09:15:50

aceasi problema ca si vidrean... ne poate ajuta cineva ?

Titlul: RÄƒspuns: 1163 Tsunami
Scris de: Mihai Visuian din Februarie 14, 2012, 09:20:57

coman cate matrici ai folosit

Titlul: RÄƒspuns: 1163 Tsunami
Scris de: Boaca Cosmin din Februarie 16, 2012, 14:52:08

Pai la tine pentru fie apel al functiei fill se pun 5 inturi pe stiva , xnou ,ynou ,d, si cei 2 parametri . La acestia se adauga variabilele globale , adica matricea efectiva care ocupa cam 4mb , avand 1 milion de variabile int . Cum pe unele teste se poate parcurge toata matricea se poate ajunge la un nr f mare de apeluri ale functiei fill , depasind memoria de 16 mb . La 700000 de apeluri ale functiei fill memoria alocata depaseste 16 mb . Te-as sfatui sa incerci cu lee . Merge foarte bine din pct. de vedere al timpului si al memoriei . Daca totusi vrei neaparat fill poti incerca optimizarea fill-ului folosind variabile de tip short .

Titlul: RÄƒspuns: 1163 Tsunami
Scris de: UBB Bora Dan din Februarie 16, 2012, 19:45:02

Nu inteleg ce n-am facut bn la problema asta de iau 10 pct (pe restu teste lor iau Killed by signal si incorect):sad:
Nu am facut cu Lee dar am facut in felul urmator: am bordat matricea apoi am parcurs-o si cand un element era >0; <h; si se invecina cu apa il inundam (ii dadeam valoarea 0) si incrementam un contor; apoi valoarea contorului era raspunsul
:annoyed: :annoyed: :annoyed: :annoyed: :annoyed: :annoyed:

Titlul: RÄƒspuns: 1163 Tsunami
Scris de: Vidrean Mihai din Februarie 17, 2012, 14:59:55

Eu am facut simplu cu o coada din stl in care am introdus la citire toate zonele cu 0 si dupaia am facut un fel de Lee care adauga in coada fiecare zona inundabila si o variabila care creste cand se introduce un element in coada.Cred ca merge si cu o coada simpla ( sir),ideea este ca trebuie facut iterativ pt. ca dupa cum a explicat Boaca Cosmin daca faci revursiv depaseste 16 mb stiva ;).

Titlul: RÄƒspuns: 1163 Tsunami
Scris de: Crestez Paul din Martie 06, 2012, 07:20:17

si eu si un coleg avem aceeasi problema:killed by signal 11
de asemenea am luat testele de la oni si,uimitor,imi da aceeasi eroare si in mingw
ies undeva din stiva sau ceva?

Cod:

#include <stdio.h>
FILE *f,*g;
char a[1005][1005];
long s;
int n,m,h,i,j,k;
long cauta(int ii,int jj)
{
long aux;
aux=1;
a[ii][jj]=0;
if((a[ii][jj-1]<h)&&(a[ii][jj-1])){aux=aux+cauta(ii,jj-1);}
if((a[ii][jj+1]<h)&&(a[ii][jj+1])){aux=aux+cauta(ii,jj+1);}
if((a[ii+1][jj]<h)&&(a[ii+1][jj])){aux=aux+cauta(ii+1,jj);}
if((a[ii-1][jj]<h)&&(a[ii-1][jj])){aux=aux+cauta(ii-1,jj);}
return aux;
}
int main()
{
f=fopen("tsunami.in","r");
g=fopen("tsunami.out","w");
fscanf(f,"%d%d%d",&n,&m,&h);
for(i=1;i<=n;i++){
	      a[i][0]=11;
	      a[i][m+1]=11;
		 }
for(j=1;j<=m;j++){
	      a[0][j]=11;
	      a[n+1][j]=11;
		 }
for(i=1;i<=n;i++){
  for(j=1;j<=m;j++){
	  fscanf(f,"%d",&k);
	  if(k>=11){a[i][j]=11;}
	  else{a[i][j]=k;}
		   }
		 }
  s=0;
for(i=1;i<=n;i++){
  for(j=1;j<=m;j++){
	     if((a[i][j]<h)&&(a[i][j])){
       if((a[i][j-1]==0)||(a[i][j+1]==0)||(a[i+1][j]==0)||(a[i-1][j]==0)){
		      s=s+cauta(i,j);
									 }
			  }
		   }
		 }
fprintf(g,"%d",s);
fclose(f);
fclose(g);
return 0;
}

Editat de moderator: Foloseste tagul code pentru a afisa codul sursa.

Titlul: RÄƒspuns: 1163 Tsunami
Scris de: Simoiu Robert din Martie 11, 2012, 10:13:33

Luati KBS pentru ca iasa din memoria stivei, deoarece fill-ul il faceti recursiv, si nu aveti destula memorie. Bagati fill iterativ, si o sa se rezolve :).

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Savin Tiberiu din Mai 06, 2011, 14:45:59