algorithm - 请从 Code Jam 2009 解释这个算法

Question

这是来自 round 1B 2009 Problem C "Square Math" 的问题.我知道比赛分析已发布。但是当一个节点可以被多次访问时，我并没有了解如何实现 BFS。我只能使用 DFS 来实现。 (因为上下文在递归 DFS 中隐式保存)。如何使用 BFS 做到这一点？

Answer 1

您必须显式保存上下文。

对于每个数字单元格，保留一个表格，其中包含可以由终止于该单元格的长度为 N 的路径产生的所有总数，以及对于每个总数，产生它的最佳路径。

对于 N=1，此数据很容易生成(每个单元格有一个简单的路径)并且给定 N 的表格，您可以通过扩展每个路径很容易地为下一个更大的 N 生成表格。