CODEWITHSUNDEEP
algorithmdata-structuresbreadth-first-search
nowonder
nowonder

Reputation: 335

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?

Upvotes: 0

Views: 235

Answers (1)

Jason Orendorff
Jason Orendorff

Reputation: 45116

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.

Upvotes: 1

Related Questions