S'il vous plaît expliquer cet algorithme de Code Jam 2009

Question

Ceci est un problème de round 1B 2009 Problem C "Square Math". Je sais que l'analyse du concours est affichée. Mais je ne comprends pas comment implémenter BFS lorsqu'un nœud peut être visité plus d'une fois. Je ne pouvais que mettre en œuvre en utilisant DFS. (parce que le contexte est sauvegardé implicitement dans DFS récursif). Comment faire cela en utilisant BFS?

Answer 1

Vous devez enregistrer le contexte explicitement.

Pour chaque cellule de nombre, conservez un tableau de tous les totaux pouvant être produits par les chemins de longueur N se terminant à cette cellule et, pour chaque total, le meilleur chemin qui le produit. Pour N = 1, ces données sont facilement produites (un chemin trivial pour chaque cellule) et étant donné les tables pour un N donné, vous pouvez facilement produire les tables pour le N suivant en étendant chaque chemin.