0

これはラウンド 1B 2009 問題 C「Square Math」の問題です。コンテスト分析が掲載されていることを知っています。しかし、ノードに複数回アクセスできる場合に BFS を実装する方法についてはわかりません。DFSを使用してのみ実装できました。(コンテキストは再帰的 DFS で暗黙的に保存されるため)。BFSを使用してそれを行う方法は?

4

1 に答える 1

1

コンテキストを明示的に保存する必要があります。

数値セルごとに、そのセルで終わる長さ N のパスによって生成できるすべての合計と、合計ごとにそれを生成する最適なパスのテーブルを保持します。

N=1 の場合、このデータは簡単に生成され (セルごとに 1 つの単純なパス)、特定の N のテーブルが与えられた場合、各パスを拡張することで、次に大きな N のテーブルを非常に簡単に生成できます。

于 2009-12-06T13:24:33.210 に答える