Modi efficienti per trovare i quadrati racchiusi da un tracciato ai loro bordi

-1

Se abbiamo una griglia 2d (ad es. punti ad ogni (x, y) tale che x e y sono numeri interi) e un percorso chiuso su questa griglia, tale che un punto sul percorso (x, y) possa essere solo seguito da un punto in [(x + 1, y), (x-1, y), (x, y + 1), (x, y-1)], qual è il modo più efficace per trovare i quadrati racchiusi da questo percorso?

Modifica: questa non è una domanda per i compiti a casa, sebbene possa essere letta come tale.

Il mio approccio attuale è, per ogni quadrato della griglia che potrebbe essere parte del percorso, conteggiare come i bordi si trovano nella stessa colonna, sotto il quadrato. Se questo è dispari il quadrato è racchiuso, e se è pari, non lo è.

Questo è O (n ^ {3}), dove n è la larghezza del percorso. C'è un modo migliore?

Per rendere "efficiente" più preciso: minore complessità temporale.

    
posta Rrab 01.09.2016 - 18:02
fonte

1 risposta

1

Calcola il rettangolo di chiusura minimo. Scansione di ogni riga del rettangolo conteggio degli attraversamenti dei bordi. Quando il conteggio è dispari, un quadrato si trova all'interno del rettangolo, quando anche fuori.

----------         ----------
| inside | outside | inside |
|        |---------|        |
    
risposta data 01.09.2016 - 18:33
fonte

Leggi altre domande sui tag