Q:

Please explain this algorithm from Code Jam 2009 

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?

A:

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.

