Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
这是2009 年第 1B 轮问题 C“平方数学”中的问题。我知道比赛分析已发布。但是当一个节点可以被多次访问时,我并没有讨论如何实现 BFS。我只能使用 DFS 来实现。(因为上下文隐式保存在递归 DFS 中)。如何使用 BFS 做到这一点?
您必须明确保存上下文。
对于每个数字单元格,保留一个表格,其中列出了可以通过在该单元格处结束的长度为 N 的路径产生的所有总计,以及对于每个总计,产生它的最佳路径。
对于 N = 1,此数据很容易生成(每个单元格有一个简单的路径)并且给定给定 N 的表格,您可以通过扩展每条路径很容易地为下一个更大的 N 生成表格。