[java] Ordinare matrice

[lordalex]

Salve a tutti, stò tentando(invano) di trovare un buon algoritmo che mi calcoli le distanze in una matrice. Il problema è questo: ho una matrice 5 x 5, ordinata da 0 a 24, in questo modo

0 1 2 3 4
5 6 7 8 9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24

ecco data una posizione di partenza, devo trovare a che distanza si trova una nuova posizione(ad esempio da 0 a 12 mi deve restituire 3).Considero di ordine 1 lo spostamento obliquo.
Ho provato con vari switch\case o con if ma viene troppo lungo, qualche consiglio????

[Patrick Jane]

Originariamente inviato da lordalex
Salve a tutti, stò tentando(invano) di trovare un buon algoritmo che mi calcoli le distanze in una matrice. Il problema è questo: ho una matrice 5 x 5, ordinata da 0 a 24, in questo modo

0 1 2 3 4
5 6 7 8 9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24

ecco data una posizione di partenza, devo trovare a che distanza si trova una nuova posizione(ad esempio da 0 a 12 mi deve restituire 3).Considero di ordine 1 lo spostamento obliquo.
Ho provato con vari switch\case o con if ma viene troppo lungo, qualche consiglio????

Se è come credo d'aver capito io, la cosa è molto semplice.

0   1  2  3  4
5   6  7  8  9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24

Però vorrei un chiarimento..

Fissiamo la posizione 0 (di partenza) e la nuova posizione 14. Questa, quanto dovrebbe restituire?

[lordalex]

da 0 a 14 deve restituire 4.
Considera che lo spostamento vale 1, sia in orizzontale che in verticale che obliquo, non mi importa sapere da dove passa.

[desa]

Ho lavorato un po' su problemi di questo tipo in passato... io farei un ragionamento di questo tipo:
- se i due numeri sono sulla stessa linea diagonale, la distanza è data dallo spostamento lungo la diagonale;
- se i due numeri NON sono sulla diagonale, la distanza è data dallo spostamento lungo la diagonale PIU' lo spostamento rimanente (che sarà tutto in orizzontale oppure tutto in verticale).
Si può poi vedere che il secondo caso in realtà li raggruppa entrambi (nel primo caso, lo spostamento rimanente è pari a 0) e quindi hai una sola condizione da codificare.
Ti propongo un algoritmo di questo tipo:
- trovi le coordinate del primo numero
- trovi le coordinate del secondo numero
- calcoli separatamente la distanza orizzontale e la distanza verticale (in valore assoluto)
- ottieni la prima parte della distanza come la minima fra la distanza orizzontale e la distanza verticale
- ottieni la seconda parte della distanza come la differenza (in valore assoluto) fra la distanza orizzontale e la distanza verticale
- sommi le due parti appena ottenute

Ti è chiaro cosa faccio? Provo a postarti una rappresentazione grafica dell'idea di base da cui sono partito:

  0 1 2 3 4 5 6 7
  ---------------
0|* * * * * * * *
1|* * * * * * * *
2|* 0 * * * * * *
3|* * * * * * * *
4|* * * * * * * *
5|* * * * * * * *
6|* * * 0 * * * *
7|* * * * * * * *

[Patrick Jane]

Originariamente inviato da lordalex
da 0 a 14 deve restituire 4.
Considera che lo spostamento vale 1, sia in orizzontale che in verticale che obliquo, non mi importa sapere da dove passa.

Ok, in sostanza ogni volta che ti sposti sommi 1.

Ma c'è una cosa che non mi torna..

da 0 a 12 torna 3; da 0 a 14 torna 4, perchè?

[lordalex]

@desa: sì, è chiara come idea, potrebbe essere l'idea che adotterò, grazie!!!!
@Patrick Jane: ho sbagliato infatti, da 0 a 12 deve restituire 2 e non 3, avevo sbagliato a contare nella matrice che avevo fatto!

[lordalex]

@desa: qualche proposta tu??

[desa]

Fammi sapere come è andata a finire!

[lordalex]

@ desa:
la prima parte l'ho capita e fatta, non capisco questa:

- ottieni la prima parte della distanza come la minima fra la distanza orizzontale e la distanza verticale
- ottieni la seconda parte della distanza come la differenza (in valore assoluto) fra la distanza orizzontale e la distanza verticale


cioè? scusa ma sono duro

Pensavo sennò: quando ho la differenza in valore assoluto delle distanze in orizzontale e verticale, posso fare Math.max(distanzaOrizzontale, distanzaVerticale), che ne dici?

[desa]

Allora, innanzitutto preferisco parlare informalmente di "spostamento", piuttosto che di "distanza": è la stessa identica cosa, per carità, ma pensare in termini di "passi" da fare per spostarsi da un numero ad un altro (e dunque, da una posizione dotata di coordinate ad un altra nella matrice) mi sembra più intuitivo e vicino alla vita di tutti i giorni.

Dunque, la questione base è che il modo più veloce per andare da un punto ad un altro è in linea retta. Ovviamente in una matrice fare questo non è possibile: si tratta di un'entità discreta e non continua. Lo spostamento diagonale è comunque molto vantaggioso: spostandosi di un solo passo in diagonale si guadagnano contemporaneamente sia un passo in orizzontale, sia uno in verticale.
Pertanto, scrivendo

ottieni la prima parte della distanza come la minima fra la distanza orizzontale e la distanza verticale

voglio dire "spostati in diagonale finchè puoi, fermandoti prima di andare oltre la linea orizzontale oppure verticale del numero che vuoi raggiungere". E, per quanto ho detto prima sui passi guadagnati spostandosi in diagonale, questo lo ottieni prendendo la distanza minima fra la orizzontale e la verticale.

A questo punto ti troverai in una posizione situata sulla stessa riga (o colonna) del numero che vuoi raggiungere. Lo spostamento mancante avverrà dunque tutto in linea retta, o in orizzontale o in verticale. E questo spostamento lo ottieni con l'ultimo step dell'algoritmo che ho definito, spostandoti di un numero di passi pari alla massima fra distanza orizzontale e verticale, a cui devi però sottrarre lo spostamento già "implicitamente" compiuto muovendoti in diagonale (e quindi la minima fra le due distanze).

Bene, detto tutto ciò, mi sono reso conto che in realtà (sempre per le proprietà dello spostamento in diagonale) tutto questo giro è ridondante e che è sufficiente l'ultima formula che hai scritto tu, in quanto

distanza_minima + (distanza_massima - distanza_minima)

è ovviamente uguale a "distanza_massima"...