I got an AC with dynamic programming and without a graph and I am frustrated with my memory consumption. I used C++ for this and i've got 0,31s and 16000 KB. I guess my solution consumed so much memory because I've stored 2 matrices, one for grid second for diagonales.
Matrix[i][j] = min (Matrix[i-1][j]+100, Matrix[i][j-1]+100, Matrix[i-1][j-1] + Diag[i][j]) where Diag[i][j] is either 100 * sqrt(2) or Infinity. I wonder if there is a better solution. I think a simple BFS could give me an answer, Bellman-Ford and Dijkstra's algorithms will give it for sure though. Nevertheless, I've never worked with a graph where every vertex is a 2D point. How should i store it? vector <int> g[maxN][maxN] ? How do I fill it with values efficently?
I think the main cause of memory consumption is the matrix of DOUBLES. Even a simple array of doubles consumes a lot of memory. Even for the solution involving graph and shortest paths would use 'huge' amount of memory, since you would also need a 2 dimensional array of doubles (I suppose). I managed to solve it using 9360KB.
a better solution is to use dynamic programming to find the longest increasing sequence of diagonals, which there are 100 at most. then ``` min = (n + m - maxDiagonals * 2) * distance + maxDiagonals * diagonalDistance ```