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?S'il vous plaît expliquer cet algorithme de Code Jam 2009
0
A
Répondre
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.
Questions connexes
- 1. S'il vous plaît expliquer jQuery
- 2. S'il vous plaît expliquer regex
- 3. C s'il vous plaît aider à expliquer peu de code
- 4. Pouvez-vous expliquer ce que fait cet extrait de code?
- 5. S'il vous plaît expliquer ce code Objective-C
- 6. S'il vous plaît expliquer ce que ce code jquery fait
- 7. S'il vous plaît expliquer hash murmur?
- 8. quelqu'un peut-il expliquer cet extrait de textmate javascript à moi s'il vous plaît
- 9. S'il vous plaît expliquer ce comportement python
- 10. rails belongs_to has_many s'il vous plaît expliquer
- 11. S'il vous plaît expliquer. ./ab_project_setup.ksh déclaration
- 12. héritage Java - s'il vous plaît expliquer
- 13. Problème avec DataBindings, expliquer s'il vous plaît
- 14. Pouvez-vous s'il vous plaît me parler de cet avertissement?
- 15. S'il vous plaît aidez-moi à accélérer cet algorithme de mahjong
- 16. Pouvez-vous s'il vous plaît expliquer surCréer et Bundles?
- 17. Pouvez-vous m'aider à comprendre cet algorithme?
- 18. S'il vous plaît expliquer les méthodes d'extension pour moi
- 19. Quelqu'un peut-il s'il vous plaît expliquer COMTIMEOUTS pour moi?
- 20. Pouvez-vous expliquer ce code?
- 21. S'il vous plaît expliquer cette étrange ligne Javascript
- 22. Pseudocode de cet algorithme
- 23. Quelqu'un peut-il expliquer cet extrait de code en PHP?
- 24. Qu'est-ce que WCS? S'il vous plaît expliquer
- 25. S'il vous plaît expliquer cette suppression top 100 syntaxe SQL
- 26. S'il vous plaît expliquer Action dans Struts 2.0 fichier XML
- 27. Quelqu'un peut-il expliquer C# CngKey.Create s'il vous plaît?
- 28. S'il vous plaît expliquer ce Convert.ToInt64 InputStringFormat Exception
- 29. S'il vous plaît expliquer deux lignes à moi
- 30. Graines Acegi Plugin - PersonController.groovy - S'il vous plaît expliquer!
Thnx. C'est un très bon algo. Est-ce que ça fait du BFS d'une manière différente? – nowonder
Il est encore appelé recherche de largeur d'abord. Garder une trace de toutes les extrémités lâches est un peu plus compliqué, c'est tout. –