Please explain the algorithm for this problem from code jam 2009

Question

This is problem from round 1B 2009 Problem C "Square Math". I know contest analysis is posted. But I am not getting on how to implement BFS when a node can be visited more than once. I could only implement using DFS. (because context is saved implicitly in recursive DFS). How to do that using BFS?

Answer 1

You have to save the context explicitly.

For each number cell, keep a table of all totals that can be produced by paths of length N ending at that cell and, for each total, the best path that produces it.

For N=1, this data is easily produced (one trivial path for each cell) and given the tables for a given N, you can produce the tables for the next larger N pretty easily by extending each path.