Пожалуйста, объясните этот алгоритм из Code Jam 2009

Question

Это задача из раунда 1B 2009 Задача C "Квадратная математика" . Я знаю, что конкурсный анализ опубликован. Но я не понимаю, как реализовать BFS, когда узел можно посетить более одного раза. Я мог реализовать только с использованием DFS. (потому что контекст сохраняется неявно в рекурсивной DFS). Как это сделать с помощью BFS?

Answer 1

Вы должны явно сохранить контекст.

Для каждой числовой ячейки ведите таблицу всех итогов, которые могут быть получены путями длины N, заканчивающимися в этой ячейке, и для каждого итога - наилучшим путем, который ее производит.

Для N = 1 эти данные легко создаются (один тривиальный путь для каждой ячейки), и, учитывая таблицы для данного N, вы можете довольно легко создать таблицы для следующего большего N, расширив каждый путь.