[TEMA] Problema cu "romburi" - segmentation fault / timp de executie foarte mare

Este vorba despre problema http://www.pbinfo.ro...probleme&id=600 .

Nu prea inteleg ce am gresit si nu stiu cum sa remediez. Rularea sursei ia aproximativ 4 secunde si imi returneaza un raspuns gresit fata de cel din exemplu. As fi recunoscator daca m-ati putea ajuta .

Multumesc pentru timpul acordat.

#include <fstream>
using namespace std;
ifstream fin("romburi.in");
ofstream fout("romburi.out");
int A[1001][1001];
int main()
{
	int n, m, romburi;
	fin >> n >> m >> romburi;
	int N, M, L;
	int X, Y, YY;
	int cate;
	int nemarcate = 0;
	for( int i = 1; i <= romburi; ++i )
	{
		fin >> N >> M >> L;
		A[N][M]++; // marchez prima casuta, cu coordonatele N si M.
		cate = 3;
		// ^ continuam de la 3 casute pana cand ajungem la diagonala paralela cu orizontala ( cate = 2 * L - 1 )
		X = N, Y = M;
		for( ; cate <= 2 * L - 1; cate += 2 )
		{
			X -= 1, Y -= 1;
			YY = Y;
			for( int k = 1; k <= cate; ++YY, k++ )
				if( (X > n || X < 1) && (YY > m || YY < 1) )
					break;
				else
					A[X][YY]++;
		}
		cate -= 2; // incep cu 2 casute mai putin, procedeul fiind simetric
		for( ; cate <= 1; cate -= 2 )
		{
			X -= 1, Y += 1;
			YY = Y;
			for( int k = 1; k <= cate; ++YY, k++ )
				if( (X > n || X < 1) || (YY > m || YY < 1) )
					break;
				else
					A[X][YY]++;
		}
	}
	for( int i = 1; i <= n; ++i )
		for( int j = 1; j <= m; ++j )
			if( !A[i][j] )
				nemarcate++;
	fout << nemarcate;
	return 0;
}

Vectorii avand n elemente se indexeaza in C/C++/C#/Java de la 0 la n - 1
Apoi iti da raspuns gresit sau segmentation fault? E o mare diferenta.
Fault-ul il detectezi cu debuggerul destul de usor pe cand o rezolvare gresita trebuie s-o iei personal la bani marunti (eu de exemplu nu inteleg ce ai vrut sa scrii prin for( int k = 1; k <= cate; ++YY, k++), valabil si pentru altii)

Edited by dani.user, 28 January 2015 - 14:31.

Nu iti inteleg remarca.

Eu am ales sa indexez matricea de la 1 la n, asa-mi vine mie mai usor. Am adaugat la dimensiune 1 ca sa nu ies din matrice.

LE: Prin acel for marchez, pe rand, "casutele acelea". Consideram desenul atasat mai jos. De la prima casuta, coboram in diagonala, si incepem cu prima casuta de pe al doilea rand. Trebuie sa marcam, pe rand, fiecare casuta. De aceea incrementez YY, ca sa marchez elementul de coordonate X, YY. De asemenea, incrementez variabila "k" pentru a sti cate elemente am marcat pana acum.

[ http://www.pbinfo.ro/resurse/probleme/600/romb.png - Pentru incarcare in pagina (embed) Click aici ]

Edited by razvanw0w, 28 January 2015 - 14:42.

1. De min, max ai auzit? Daca nu, stii sa faci un macrou sau o functie pentru a afla minimul, respectiv maximul a 2 numere?
2. Pt lungimea 1, cam ce face codul tau?
3. Ce crezi ca face break?
Test pentru 3:
10 10 1
2 2 7

Edited by Cy_Cristian, 28 January 2015 - 14:58.

1. Da, am auzit de functiile min si max, cele din biblioteca algorithm, dar nu vad cu ce m-ar putea ajuta in aceasta problema.
2. Marcheaza o singura "casuta", cea de coordonate specificate(teoretic asta ar trebui sa faca).
3. Atunci cand trebuie sa accesez o "casuta" care nu se afla in matrice, am pus acel "break" pentru a preveni segmentation fault(cel putin asta era intentia mea).

Output-ul pentru testul tau este 150 de casute nemarcate, pentru o matrice de 12x13.

Inteleg ca n-ai facut nimic din ce ti-am zis eu.
1. Studiaza unde ti-ar trebui.

2. Nici macar n-ai incercat sa rulezi codul cu un astfel de test. Raspunsul corect este: marcheaza 2 celule. Cel mai grav este ca-ti ia 20 de secunde sa faci un test, dar n-ai vrut sa "irosesti" atata timp pe "prostia debitata" de mine.
10 10 1
5 5 1
Raspunsul corect ar fi trebuit sa fie 99. Dar tu produci 98.
Problema este ca programul excuta ce l-ai programat sa faca si nu ce crezi tu ca l-ai programat.

3. Fa pe foaie testul pe care ti l-am dat si o sa vezi greseala. Dupa aia, poate o sa vezi de ce te-am intrebat de min si max.

Tot ce ti-am zis am dedus doar citind codul. Poate ar fi cazul sa lasi modestia si sa intelegi ca noi incercam sa te ajutam.

Edited by Cy_Cristian, 28 January 2015 - 16:24.

Ai dreptate. Am interpretat gresit testul tau si am obtinut un rezultat total diferit fata de ceea ce voiai tu sa observ. Imi cer scuze pentru neplacerile cauzate. O sa fac testul acela pe foaie si o sa revin cu un LE.

Imi cer scuze pentru acest post, sper sa nu fiu sanctionat pentru double post, dar nu mai pot edita raspunsul precedent.

Am facut acel test si am observat ca daca pun break, chiar daca o linie are si celule ce pot fi marcate in interiorul matricii, daca linia incepe din afara matricii, trece direct la linia urmatoare. Am facut niste modificari, dar pentru testul cu 2 2 7 imi afiseaza 49 in loc de 53. Chiar nu mai am nicio idee cum pot remedia codul. Sper sa imi puteti da o indicatie astfel incat sa-l pot remedia.. Aveti codul mai jos. Multumesc.

#include <fstream>
using namespace std;
ifstream fin("romburi.in");
ofstream fout("romburi.out");
int A[1001][1001];
int main()
{
	int n, m, romburi;
	fin >> n >> m >> romburi;
	int N, M, L;
	int X, Y, YY;
	int cate;
	int nemarcate = 0;
	for( int i = 1; i <= romburi; ++i )
	{
		fin >> N >> M >> L;
		A[N][M]++; // marchez prima casuta, cu coordonatele N si M.
		cate = 3;
		// ^ continuam de la 3 casute pana cand ajungem la diagonala paralela cu orizontala ( cate = 2 * L - 1 )
		X = N, Y = M;
		for( ; cate <= 2 * L - 1; cate += 2 )
		{
			X += 1, Y -= 1;
			YY = Y;
			for( int k = 1; k <= cate; ++YY, k++ )
			{
				if( X > m || X < 1 )
					break;
				if( (YY > m || YY < 1) )
					continue;
				A[X][YY]++;
			}
		}
		cate -= 2; // incep cu 2 casute mai putin, procedeul fiind simetric
		for( ; cate > 1; cate -= 2 )
		{
			X += 1, Y += 1;
			YY = Y;
			for( int k = 1; k <= cate; ++YY, k++ )
			{
				if( X > m || X < 1 )
					break;
				if(YY > m || YY < 1)
					continue;
				A[X][YY]++;
			}
		}
		if( L > 1 )
		{
			X += 1, Y += 1;
			YY = Y;
			for( int k = 1; k <= cate; ++YY, k++ )
			{
				if( X > m || X < 1 )
					break;
				if(YY > m || YY < 1)
					continue;
				A[X][YY]++;
			}
		}
	}
	for( int i = 1; i <= n; ++i )
		for( int j = 1; j <= m; ++j )
			if( !A[i][j] )
				nemarcate++;
	fout << nemarcate;
	return 0;
}

deci ai o matrice mare, sau un teren
pe care incepi sa-l marchezi, sau sa-l decupezi
un numar de romburi

iar in final trebuie sa vezi cate casute mai ai libere.

matematica mai simpla de atat n-am vazut
singurul lucru interesant este cum desenezi romburile

Pai desenarea romburilor e putin mai complicata. Am avut niste greseli in cod in posturile de mai sus, iar acum le-am corectat, dar totusi, ceva nu e bine si nu-mi dau seama ce..

de ce e complicata?
faci functie separata care sa deseneze, intr-un camp trimis ca parametru

1. Faptul ca X este doar incrementat nu mai trebuie facut testul cu X<1. In plus. din moment ce ai trecut sub grid, nu mai trebuie sa continui. Deci testul se face in afara celui de-al doilea for si nu in interior.
2. Ti-am sugerat sa folosesti min si max pentru deplasarea pe orizontala. Acolo aveai si probabil ca mai ai problema de performanta.
3. Incearca sa faci "desenarea" intr-un singur for. Vezi cand trebuie incrementat Y-ul si cand decrementat.

Iti sugerez pix si foaie.
Incep eu cu logica: Daca L este dimensiunea, in general vor fi 2*L-1 randuri
Pe randul k va avea x celule  ... (formula in functie de randul curent si dimensiunea rombului).
Voi incrementa/decrementa Y in functie de randul curent si L astfel ....

LE:
Ce face partea asta de cod?

				cate -= 2; // incep cu 2 casute mai putin, procedeul fiind simetric
				for( ; cate > 1; cate -= 2 )
				{
						X += 1, Y += 1;
						YY = Y;
						for( int k = 1; k <= cate; ++YY, k++ )
						{
								if( X > m || X < 1 )
										break;
								if(YY > m || YY < 1)
										continue;
								A[X][YY]++;
						}
				}
				if( L > 1 )
				{
						X += 1, Y += 1;
						YY = Y;
						for( int k = 1; k <= cate; ++YY, k++ )
						{
								if( X > m || X < 1 )
										break;
								if(YY > m || YY < 1)
										continue;
								A[X][YY]++;
						}
				}

Edited by Cy_Cristian, 28 January 2015 - 18:05.

Scuzati-mi intarzierea, am avut niste probleme si nu am putut sa postez.

Din fericire, am putut rezolva problema datorita indicatiilor lui Cristian( printr-o desenare cu un singur for, parcurgand liniile pana la 2L-1 ).

Multumesc frumos pentru rabdare si atentia acordata!