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.