请从编程挑战赛2009年

Question

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

Answer 1

你必须明确地保存上下文。

对于每个编号单元，保持可以由在该小区结束的长度N路径来生产，并且对于每个总，产生它的最佳路径所有总量的表。对于N = 1，这个数据很容易产生（每个单元一条简单的路径）并且给定N的表，通过扩展每条路径，可以很容易地生成下一个更大的N的表。