By Eduard Ionescu

The intended solution involved finding the minimum sum of the densities required to reach each tile (running DP on the grid). More specifically, move from left to right obtaining the sum by adding the value of the current tile to the minimum of the one on its left, right, or above. You will also have to run through each length twice as you can move to the left as well. To better understand the problem, it is recommended that you create a case where the cheapest path includes moving to the left.

Time Complexity: ~\mathcal{O}(LD)~

Note: Some participants solved it using Dijkstra's Shortest Path Algorithm, as the grid could be represented as a weighted graph with non-negative edges. However, this is a suboptimal solution and only passes due to the lenient time limit.

Time Complexity: ~\mathcal{O}(LD \log(LD))~, using a binary heap