Qualcuno può spiegare questa formula per il calcolo della distanza di Manhattan?
-
05-11-2019 - |
Domanda
Questo è da a Problema di kickstart:
Notare la Distanza di Manhattan Tra due quadrati (R1, C1) e (R2, C2) è definito come | R1 - R2 | + | C1 - C2 |, dove |*| L'operatore indica il valore assoluto.
Quindi nell'analisi:
Si noti che la distanza di Manhattan ha una formula equivalente:
dist((x1, y1), (x2, y2)) = max(abs(x1 + y1 - (x2 + y2)), abs(x1 - y1 - (x2 - y2)))
Questa formula si basa sul fatto che per qualsiasi punto, l'insieme di punti all'interno di una distanza di Manhattan di K forma un quadrato ruotato di 45 gradi. Il vantaggio di questa formula è che se fissiamo (x2, y2), la distanza verrà massimizzata quando x1 + y1 e x1 - y1 sono massimizzati o minimizzati.
Qualcuno potrebbe spiegare in modo più dettagliato come può essere derivata questa formula?
Nessuna soluzione corretta
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange