It is an old question. I met it in a computer science class in 1983/4, where I think it had previously been an exam question. The discussion in class went round in circles considering various recursive approaches. I think we missed main idea. Or perhaps I just didn't understand at the time.
Think of it as a single-source shortest path problem. The surrounding sea is the single source. Instead of minimizing path distance from each cell to the sea you seek to minimize the height of the lowest barrier between each cell and the sea. Dijkstra's shortest path algorithm is the way to go, with a fringe of cells kept in a priority queue. WC Leung's answer is exactly right. For an exam question in about 1980, even when you have recently attended an algorithms course, I still think it quite hard. -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/b9d976f7-ff28-4b96-b526-0f143fa98cde%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
