HW6 Obb test_foto_10_6_ter

a
a.pietroluongo (11250 points)
15 38 131
asked Nov 23, 2019 in HW6 obbligatorio by a.pietroluongo (11,250 points)
closed Nov 25, 2019 by a.pietroluongo
Come posso ottimizzare il test_foto_10___6_ter___40__17871_  ?
Vado in timeout 4s. (Gli altri test  sono OK)
543 views
closed with note: ho cambiato algoritmo.

3 Answers

z
zanna (510 points)
0 1 6
answered Nov 23, 2019 by zanna (510 points)
Se vai in timeout di 4 secondi potrebbe essere proprio il tuo algoritmo a non andare bene (nonostante funzioni per gli altri test). Sfrutta la caratteristica delle immagini di avere o non avere un segmento rosso, ti basta sapere se dopo un pixel verde c'è un solo pixel rosso per sapere con certezza che ci sarà tutto quel segmento. Inoltre pensa al fatto che è inutile controllare quelle righe e colonne da cui sicuramente non avrà inizio un quadrato.
a
a.pietroluongo (11250 points)
15 38 131
commented Nov 23, 2019 by a.pietroluongo (11,250 points)
Si, faccio entrambi i controlli..
fc-dev (16450 points)
12 20 34
commented Nov 24, 2019 by fc-dev (16,450 points)
Ah... quindi basta un solo pixel... ?
Non c'è la possibilità di segmenti parzialmente vuoti?
Tommaso Sgroi (12990 points)
6 11 91
commented Nov 24, 2019 by Tommaso Sgroi (12,990 points)
No, i segmenti non possono essere parzialmente vuoti.
Tommaso Sgroi (12990 points)
6 11 91
answered Nov 24, 2019 by Tommaso Sgroi (12,990 points)

Il codice deve essere valido per ogni input, quindi non si può scrivere un qualcosa di specifico (in questo caso foto_10___6_ter), il consiglio però che ti posso dare è di cercare di eliminare cicli superflui e di non considerare tutti i pixel tra i verdi, perché se anche solo uno di essi è nero o rosso allora lo saranno anche i restanti tra i 2. Sopratutto non devi arrivare per forza fino all'ultimo pixel della tua griglia, e le uniche coordinate essenziali della tua griglia sono quella in alto a sx e in basso a dx (parlo dei pixel verdi).

plm (18850 points)
7 15 118
answered Nov 24, 2019 by plm (18,850 points)
Purtroppo credo che la soluzione sia ottimizare l'algoritmo o ripensarlo da capo siccome non si può modellare l'algoritmo per farlo andare bene in un test solo, ma bensì di essere efficente per ogni problema proposto.