Parcurgere matrice in spirala

Vreau sa parcurg o matrice in urmatorul mod: pornind din coltul stanga sus, traverseaza element dupa element prima linie, coboara pe ultima coloana, traverseaza ultima linie de la dreapta la stanga, urca pe prima coloana, apoi continua cu cea de-a doua linie, penultima coloana, penultima linie si a doua coloana etc.
Doar ca nu stiu exact cum... Adica nu pot scrie o secventa in care sa fac parcurgerea asta.

Daca e nevoie iata si cerinta problemei: Sa se stabileasca daca spiralatabloului dat formeaza sau nu o progresie aritmetica. Prin progresie aritmetica intelegem o insiruire de numere in care diferenta dintre oricare doua numere consecutive este aceeasi

Partea asta stiu sa o fac.

r=a[1][1]-a[0][0];

si apoi ma opresc cand o diferenta din spirala e diferita de r. Dar tot nu reusesc sa fac parcurgerea aia :|

Fie:

Quote

Partea cu verde este o iteratie. Gandeste-te cum o faci pe ea mai intai, chiar si static, cu valori hard-coded.

Apoi introduce variabile intermediare astfel incat sa parcurgi oricare dintre cele 4 "bucle", caci sunt 4.

Cea mai din exterior iteratie de exemplu, incepe la indexul (0,0), urmatoarea la (1,1), si tot asa.

Daca vrei sa o faci bine, introduci si cateva functii noi. Daca vrei sa o faci excelent, inventezi o structura "matrix" cu campuri precum "width", "height", "iteration_type" si un pointer la o functie care primeste valori la fiecare iteratie... Ma rog, asta intra deja la categoria "reusable code". Poti tine minte problema asta pentru mai tarziu daca simti ca te depaseste inca.

Edited by OriginalCopy, 13 February 2010 - 16:04.

Am schimbat putin matricea data de tine ca sa ma pot verifica mai usor (mda... stiu... lenes), si am scris aseara (ca tot nu aveam ce face pe la 22):

#include<fstream.h>
#include<math.h>
int ex[7][7] = {
{ 1, 2, 3, 4, 5, 6, 7},
{ 24, 33,33,33,33,33,8},
{23,33,33,33,33,33,9},
{22,33,24,25,26,27,10},
{21,30,31,32,33,34,11},
{20,37,38,39,40,41,12},
{19,18,17,16,15,14,13}
};
int main()
{
int n=7,m=7,i,j;
ofstream out("date.out");
for(j=0;j<=m-1;j++)
	out<<ex[0][j]<<" ";
out<<endl;
for(i=1;i<=n-1;i++)
	out<<ex[i][m-1]<<" ";
out<<endl;
for(j=m-2;j>=0;j--)
	out<<ex[n-1][j]<<" ";
out<<endl;
for(i=n-2;i>=0;i++)
	out<<ex[i][0]<<" ";
out.close();
return 0;
}

Si imi afiseaza:
1 2 3 4 5 6 7
8 9 10 11 12 13
14 15 16 17 18 19
20 19 24932 8192 525 0 310 0 0 0 0 255 0 si de aici continua cu multe valori.

Care e greseala la ultimul for?

De asemenea, exercitiul tau mi-a dat idei pentru rezolvarea problemei, dar tot asa fac niste greseli din alea de care fac de obicei.

Enunt:
      Spiral
Se considera un tablou bidimensional care contine numere intregi. Numim spirala acel drum prin matrice care, pornind din coltul stanga sus, traverseaza element dupa element prima linie, coboara pe ultima coloana, traverseaza ultima linie de la dreapta la stanga, urca pe prima coloana, apoi continua cu cea de-a doua linie, penultima coloana, penultima linie si a doua coloana etc. Drumul se opreste undeva in tablou, dupa ce toate elementele au fost traversate. Fiecare element se atinge o singura data.
Cerinta
Sa se stabileasca daca spiralatabloului dat formeaza sau nu o progresie aritmetica. Prin progresie aritmetica intelegem o insiruire de numere in care diferenta dintre oricare doua numere consecutive este aceeasi (pentru un sir de N numere, ai - ai+1 = dif, i = 1, 2, ..., n - 1).
In cazul in care raspunsul este afirmativ, sa se determine valoarea ultimului element din spirala, in caz contrar sa se afiseze valorile primelor doua elemente din spirala ale caror diferenta nu este egala cu diferenta dintre valorile elementelor verificate.
Date de intrare
Pe prima linie a fisierului de intrare spiral.in se afla doua numere naturale (nrlin si nrcol), reprezentand numarul liniilor, respectiv numarul coloanelor din tablou. Pe urmatoarele nrlin linii se afla cate nrcol numere intregi. Oricare doua numere din fisier sunt despartite prin cate un spatiu.
Date de iesire
• Daca spirala formeaza progresie aritmetica, pe prima linie a fisierului de iesire spiral.out se va scrie cuvantul DA. Pe urmatoarea linie se va scrie valoarea ultimului element din spirala.
Daca spirala nu formeaza progresie aritmetica, pe prima linie a fisierului de iesire spiral.out se va scrie cuvantul NU. Pe urmatoarea linie se vor scrie doua numere naturale, reprezentand primele doua numere din tabloul dat in cazul carora nu este indeplinita proprietatea de progresie aritmetica.
Restrictii si precizari
• 2 ≤ nrlin, nrcol ≤ 100
• -32000 ≤ tabloui,j ≤ 32000 (i = 1, 2, ..., nrcol, j = 1, 2, ..., nrlin)
Exemple
spiral.in:
3 3
1 3 5
15 17 7
13 11 9
spiral.out:
DA
17

spiral.in:
2 3
-1 -3 -5
-15 -5 -7
spiral.out:
NU
-7 -5

Ideea mea:

#include<fstream.h>
#include<math.h>
int a[100][100];
int main()
{
int n,m,i,j,k,d=1,x1,x2,x3,x4,y1,y2,y3,y4,r,ni=1,q=0,ok=1,e;
ifstream in("spiral.in");
ofstream out("spiral.out");
in>>n>>m;
for(i=1;i<=n;i++)
	for(j=0;j<=m-1;j++)
		in>>a[i][j];
k=n*m;
r=a[1][2]-a[1][1];
x1=0;
y1=0;
x2=n;
y2=m;
x3=n;
x4=m;
y3=0;
y4=0;
do
	{
	if(d==1)
		{
		x1++;
		x2--;
		for(j=x1;j<=x2-1;j++)
			{
			q++;
			if(abs(a[ni][j]-a[ni][j+1])!=r)
				{
				out<<"NU"<<endl<<a[ni][j]<<" "<<a[ni][j+1];
				ok=0;
				break;
				}
			else
				e=a[ni][j+1];
			if(j==x2-1)
				{
				d=2;
				ni=j+1;
				}
			if(q==k-1)
				{
				ok=0;
				break;
				}
			}
		}
	if(ok==0)
		break;
	if(d==2)
		{
		y1++;
		y2--;
		for(i=y1;i<=y2-1;i++)
			{
			q++;
			if(abs(a[i][ni]-a[i+1][ni])!=r)
				{
				out<<"NU"<<endl<<a[i][ni]<<" "<<a[ni+1][ni];
				ok=0;
				break;
				}
			else
				e=a[i+1][ni];
			if(i==y2-1)
				{
				d=3;
				ni=i+1;
				}
			if(q==k-1)
				{
				ok=0;
				break;
				}
			}
		}
	if(ok==0)
		break;
	if(d==3)
		{
		x3--;
		y3++;
		for(j=x3;j>=y3-1;j--)
			{
			q++;
			if(abs(a[ni][j]-a[ni][-1])!=r)
				{
				out<<"NU"<<endl<<a[ni][j]<<" "<<a[ni][j-1];
				ok=0;
				break;
				}
			else
				e=a[ni][-1];
			if(j==y3-1)
				{
				d=4;
				ni=j-1;
				}
			if(q==k-1)
				{
				ok=0;
				break;
				}
			}
		}
	if(ok==0)
		break;
	if(d==4)
		{
		x4--;
		y4++;
		for(i=x4;i>=y4;i--)
			{
			q++;
			if(abs(a[i][ni]-a[i-1][ni])!=r)
				{
				out<<"NU"<<endl<<a[i][ni]<<" "<<a[i-1][ni];
				ok=0;
				break;
				}
			else
				e=a[i-1][ni];
			if(i==y4-1)
				{
				d=1;
				ni=i-1;
				}
			if(q==k-1)
				{
				ok=0;
				break;
				}
			}
		}
	if(ok==0)
		break;
	}
while(q!=k-1);
if(ok==1)
	out<<"DA"<<endl<<e;
in.close();
out.close();
return 0;
}

Abia azi le-am verificat si am vazut ca ceva nu-i bine...

for(i=n-2;i>=0;i++)
	out<<ex[i][0]<<" ";

pai i-a vezi la ce valori ajunge i? v-a ajunge vreodata sa nu indeplineasca conditia ca sa iasa din for? eu zic ca nu.
in plus aceste 4 for-uri ar trebui incluse intr-un while sau for.
Cam asa ar arata algoritmul:

mat[X][Y] = ...
int allElem = 0;
int chkElem = 0;
int lenX = X%2 + X/2;
	int lenY = Y%2 + Y/2;
	int tempX = X - 1;
	int tempY = Y - 1;
	int i = 0;
	while(true)
	begin
		if(![color="#FF0000"]GoRight(i, tempX, tempY)[/color]) break;
		if(![color="#0000FF"]GoDown(i, tempX, tempY)[/color]) break;
		if(![color="#00FF00"]GoLeft(i, tempX, tempY)[/color]) break;
		if(![color="#9932CC"]GoUp(i, tempX, tempY)[/color]) break;
		tempX--;
		tempY--;
		i++;
	end;

iar cele 4 functii vor parcurge matricea in felul urmator:

{ [color="#FF0000"]1, 2, 3, 4, 5, 6,[/color] [color="#0000FF"]7[/color]},
{[color="#9932CC"] 8[/color], 9,10,11,12,13,[color="#0000FF"]14[/color]},
{[color="#9932CC"]15[/color],16,17,18,19,20,[color="#0000FF"]21[/color]},
{[color="#9932CC"]15[/color],16,17,18,19,20,[color="#0000FF"]21[/color]},
{[color="#9932CC"]22[/color],23,24,25,26,27,[color="#0000FF"]28[/color]},
{[color="#9932CC"]29[/color],30,31,32,33,34,[color="#0000FF"]35[/color]},
{[color="#9932CC"]36,[/color][color="#00FF00"]37,38,39,40,41,42[/color]}
};

in functiile de parcurgere incrementezi chkElem si inainte de a iesi din functie verifici daca ai terminat de parcurs toate elementele. daca ai terminat returnezi true. si gata. nu stiu daca e cea mai buna solutie, dar cred ca merge

Uite aici o functie care iti afiseaza spirala.Ca sa verifici daca elem spiralei sunt in progresie aritmetica modifici functia astfel incat sa-ti puna elementele intr-un vector iar apoi e simplu trebuie doar sa parcurgi vectorul si sa vezi daca dif intre oricare doua elem ale vectorului e aceeasi.

void spirala(int a[20][20],int n)
{
	int lc = 0,cc = 0,i;

	while(n >= 0)
	{
		for(i = cc; i < n; i++)
			cout<<a[lc][i]<<" ";
		for(i = lc + 1; i < n; i++)
			cout<<a[i][n-1]<<" ";
		for(i = n - 2; i >= cc; i--)
			cout<<a[n-1][i]<<" ";
		for(i = n - 2; i >= lc + 1; i--)
			cout<<a[i][cc]<<" ";
		n--;
		lc++;
		cc++;
	}
}

Sper ca intelegi algoritmul ca e simplu,dar daca ai nelumuriri intreaba-ma.

Edited by Ph@ntom, 15 February 2010 - 18:45.

Vai... cum sa pun i=n;i>=0;i++?!? Mi-e rusine :|

Din pacate, saptamana asta nu prea am avut timp (da, sigur), dar cred ca i-am dat de cap. Mai ales ca am facut si cu diriga o parcurgere in spirala pentru o matricea cu numarul de linii egal cu numarul de coloane.

Multumesc

Dupa ceva timp de cautari si cercetari...m-am decis sa cer putin ajutor...am o problema de rezolvat care suna foarte banal dar totusi nu reusesc sa o fac : "Sa se afiseze elementele unei matrice citita de la tastatura in spirala.". M-am apucat de cod si aproape am reusit dar am o mica problema cu care sper ca ma poate ajuta cineva...

Problema este ca dupa afisarea elementelor unelor dintre matrici penultimul element este afisat dinou l-a sfarsit...dar nu la toate matricile...

De exemplu: La matricea 1   2   3  4
                                     5   6   7  8
                                     9  10 11 12

programul afiseaza: 1 2 3 4 8 12 11 10 9 5 6 7 6 ....

#include <iostream.h>
#include <conio.h>
void main()
{
	int n,m,i,j,k,a[100][100];
	cout<<"Numarul de linii= ";
	cin>>n;
	cout<<"Numarul de coloane= ";
	cin>>m;
	for(i=0;i<n;i++)
	for(j=0;j<m;j++)
	{
					cout<<"a["<<i<<"]["<<j<<"]= ";
					cin>>a[i][j];
	}
	k=0;
while((k<m)||(k<n))
{
for(j=k;j<m;j++)
cout<<a[k][j]<<" ";
for(i=k+1;i<n;i++)
cout<<a[i][m-1]<<" ";
for(j=m-2;j>=k;j--)
cout<<a[n-1][j]<<" ";
for(i=n-2;i>k;i--)
cout<<a[i][k]<<" ";
k++;
n--;
m--;
}
}

Acesta este codul meu. Sper ca cineva sa ma ajute. Stiu ca aceasta problema a mai fost pusa in multe alte locuri pe net, dar nu am gasit nimic care sa fie la nivelul cunostintelor mele de informatica de clasa a 11-a.

Citește ce scrie mai sus.

Dacă ai fi căutat cu adevărat, ai fi găsit. Eu am căutat după "spirala" si a durat 5 secunde. Ție ți-a luat 10-15 minute să-ți scrii problema.

Leneșul mai mult aleargă ...

Edited by OriginalCopy, 29 October 2011 - 09:35.

Multumesc mult! Desenul cu culori m-a ajutat !