Please ignore secret bonuses. Secret tests do NOT award bonus. Max hw grade is 30+2 bonus efficiency

Do you need help?

Problema soluzione HW4bis es3

M
MatteoDante (620 points)
0 3 5
in HW4bis by (620 points)
Buonasera,

Ho un problema con la risoluzione del test es3_tricky.png, non mi spiego il perchè data la traccia dell'esercizio "trovare i due punti più distanti tra di loro" per il test es3_tricky.png mi restituisce la seguente immagine

https://images2.imgbox.com/1f/2a/fAoJABE2_o.png

A destra c'è la mia soluzione mentre a sinistra si può vedere la soluzione del test

Non capisco perchè dati i due punti, la soluzione fa vedere che bisogna passare anche per il tratto della radice e poi quindi tornare indietro. se potessi ritornare indietro allora colorerei tutti i pixel bianchi di blu in quanto quello sarebbe il percorso più lungo per arrivare da un nodo ad un altro (ovvero arrivare a toccare tutti i nodi per poi tornare indietro)

Mi scuso se non sono stato abbastanza chiaro

Vi ringrazio in anticipo
498 views
closed

2 Answers

Best answer
_andrea_ (45670 points)
11 42 297
by (45.7k points)
selected by
devi colorare anche i pixel che portano alla radice perché se tu stessi percorrendo il cammino che da una foglia ti porta ad un'altra, dovresti per forza passare da un padre che hanno in comune. in questo caso le due foglie hanno come padre in comune la radice, quindi ci devono passare anche se nell'immagine esiste quel percorso alternativo
M
MatteoDante (620 points)
0 3 5
by (620 points)
Vi ringrazio per la risposta.

Mi spiego meglio Andrea, io per calcolarmi il massimo percorso ho assunto che ogni nodo rosso, uno alla volta, diventasse verde, mi calcolo allora per ogni nodo il nodo più lontano, una volta che li ho trovati tutti mi trovo il massimo tra i percorsi più lontani, e questo esce fuori... nel mio schema il verde non è padre anzi è una foglia...
_andrea_ (45670 points)
11 42 297
by (45.7k points)
È un modo interessante di calcolare il diametro ma non puoi dimenticarti che quello è comunque un albero. Immagina che la radice sia una piazza e i nodi delle piazzette, e che i pixel bianchi siano strade che le collegano. Io ti chiedo: trova il percorso più lungo da una piazzetta ad un'altra piazzetta, però devi passare sempre per la piazza che le collega. In questo caso il nodo in alto a sinistra e quello subito sotto a destra della radice sono i più lontani, ma comunque quello a sinistra è figlio della radice, quindi per arrivare all'altro devi passarci, per poi tornare indietro e cambiare strada, andando verso quel figlio che sto sotto la radice e da lì verso l'altro nodo che è da collegare. Ti stai comunque muovendo in un albero, non un'immagine normale
M
MatteoDante (620 points)
0 3 5
by (620 points)
Grazie Andrea,

Il mio focus infatti era sul tornare il percorso matematico più lungo dell'immagine e non dell'albero che si va a creare...

Cosa mi suggerisci di fare allora... io ho lavorato con gli oggetti quindi ho la radice con il suo attributo percorso che per la radice è vuoto e con l'attributo figli che è una lista di altre istanze dello stesso oggetto che a loro volta hanno il percorso del padre per arrivare fino a loro, le coordinate e i loro figli. Per calcolarmi il diametro che chiede l'esercizio posso ispirarmi a qualche documentazione o esercizio? Altrimenti sarei bloccato, non mi viene in mente un metodo per trovare il nodo più lontano da un altro nello stesso albero..
_andrea_ (45670 points)
11 42 297
by (45.7k points)
È come calcolare l'altezza ma devi calcolare le due più grandi e sommarle, e poi confrontarle con quella che già hai. Quello è il diametro
andrea.sterbini (207920 points)
750 1267 2373
by (208k points)
L'abbiamo fatto a lezione ... molto simile
M
MatteoDante (620 points)
0 3 5
by (620 points)
Professore intende la lezione 17 "Ricorsione ed Alberi"?

Comunque ho risolto ed ora consegno, grazie a entrambi.
andrea.sterbini (207920 points)
750 1267 2373
by (208k points)
L'esercizio chiede di contare tutti i punti bianchi se necessario passandoci due volte come in questo caso.
Il percorso più lungo infatti in questo caso passa per la radice per cui bisogna colorare anche quei pixel.
(e se colori di blu tutti i punti bianchi della figura ottieni che il percorso non è più lineare ma un albero che si dirama, quindi non è più "il percorso più lungo che collega due nodi dell'albero")

Spero di essermi spiegato decentemente