This is a more difficult version of problem 82, and now you can move in all four directions!
As before, we start by loading the input data into a 2D array:
and initialize another matrix of the same size to hold the minimum sum leading to each cell:
What we have done differently this time though, is to choose initial defaults:
- for the top-left corner (0, 0) the minimum sum is itself
- for all other cells at (row, col) we’ll always traverse right and then down
- if row = 0, then this equates to only move right until we reach col
- if col = 0, then this equates to only move down until we reach row
Next, as we did for the problem 82, we’ll add a couple of helper to help us traverse both matrices:
and we’ll find the new minimum sum to each cell by taking the minimum from the four directions:
Unlike before, we can’t isolate to optimizing one column at a time, and instead we’ll need to traverse the whole matrix. For better cache locality, we’ll traverse row first and recursively optimize the whole matrix until no more optimization is possible:
Finally, find the final value for the bottom-right corner of the sum matrix:
This solution runs in 73ms on my laptop.
The source code for this solution is here.