Buongiorno a chiunque legga. Sto cercando di risolvere il problema Espansione del danno, ho capito che la soluzione è l’algoritmo bfs, so come funziona nella teoria ma non so come implemetarlo in pratica. C’è un qualche video o documento che spieghi come si deve agire con l’input dato? Anche qualche problema simile da studiare sarebbe gradito.
Una volta che sai come funziona nella teoria non dovrebbe essere difficile.
Ti tieni il grafo rappresentato come una lista di adiacenza (per ogni nodo, la lista dei nodi ad esso collegati), ed esplori partendo dai nodi sorgente con una coda (Last In First Out), tenendoti le distanze per ogni nodo ed usandole per non rivisitare lo stesso nodo due volte.
cp-algorithms e usaco guide possono esserti di aiuto.
Nel problema Espansione del danno il grafo e’ una griglia, quindi potrebbe convenirti non rappresentarlo come una lista di adiacenza, ma fare lo stesso algoritmo calcolando i nodi adiacenti ad ogni passo.
1 Mi Piace