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

Do you need help?

Notice Board

Ottimizzare algoritmo Hw3 Esercizio 1

S
SkyLion (1020 points)
7 15 24
in Es1 by (1.0k points)
closed by

Ho provato a svolgere il primo esercizio dell'Homework3 andando a scorrere pixel per pixel l'ìimmagine, e se trova un pixel del colore cercato, cerca di costruirsi il quadrato più grande possibile senza andare ad incappare in un pixel di colore diverso, andando a controllare prima i lati e poi le digonali (in questo modo).

Nel caso in cui tutti i pixel controllati risultato dello stesso colore, procede a controllare tutto l'interno del quadrato perchè potrebbero essercene degli altri all'interno... Così facendo però nell'ultima istanza di test l'algoritmo impiega ben 34 secondi... Come posso ottimizzarlo?

540 views
closed with the note: deadline expired

2 Answers

by (9.9k points)
Basandomi sul tuo algoritmo, perché controlli le diagonali? Hai provato a vedere i tempi se controlli nessuna diagonale e poi una sola prima di controllare l'interno?
S
SkyLion (1020 points)
7 15 24
by (1.0k points)
Si, inizialmente il mio algoritmo controllava solo due lati, poi aggiungendone altri due ho visto che il tempo si è dimezzato... aggiungendo una diagonale ho ancora diminuito il tempo e aggiungendo anche l'altro ho dimezzato un'altra volta.
by (9.9k points)
A questo punto potresti "tagliare" il quadrato in altri modi, però stai attento perché arriverà un punto dove non conviene più "tagliare", ossia ci metteresti più tempo a fare i controlli preliminari che quelli completi.
Gianluigi (1420 points)
10 17 30
by (1.4k points)
Potresti pensare di cercare i pixel di colore diverso e salvarti la loro posizione. In questo modo saprai la posizione degli "ostacoli", e saprai se vale la pena continuare a cercare il quadrato piu' grande in una determinata posizione.