Si prega di spiegare questo algoritmo da Code Jam 2009

Question

Questo è problema da turno 1B Piazza 2009 Problem C" Math ". So che l'analisi concorso è pubblicato. Ma io non sono sempre su come implementare BFS quando un nodo può essere visitato più di una volta. Ho potuto implementare solo utilizzando DFS. (In quanto contesto viene salvato in modo implicito ricorsiva DFS). Come farlo usando BFS?

Answer 1

Si deve salvare il contesto in modo esplicito.

Per ogni cella numero, mantenere una tabella di tutti i totali che possono essere prodotti da percorsi di lunghezza N terminanti in quella cella e, per ciascuna totale, il miglior percorso che lo produce.

Per N = 1, questi dati sono facilmente prodotto (un percorso banale per ogni cella) e dato i tavoli per un dato N, è possibile produrre le tabelle per la prossima grande N abbastanza facilmente estendendo ogni percorso.