Lower memory usage when searching for optimal route from one point of matrix to another

I have following problem:

Tourist wants to create an optimal route for the hike. He has a terrain elevation map at a certain scale - an NxM-sized matrix containing the elevation values at the corresponding terrain points. Tourist wants to make a route from the start point to the end point in such a way that the total change in altitude while passing the route is minimal. The total change in altitude on the route is the sum of the changes in altitude modulo on each segment of the route. For example, if there is a continuous ascent or descent from the starting point of the route to the end point, then such a route will be optimal.

For simplicity, let's assume that you can only walk along the lines of an imaginary grid, i.e. from position (i, j), which is not on the edge of the card, you can go to position (i-1, j), (i + 1, j), (i, j-1), (i, j + 1). You cannot go beyond the edge of the map. On standard input: non-negative integers N, M, N0, M0, N1, M1 are entered. N is the number of rows in the heightmap, M is the number of columns. Point (N0, M0) is the starting point of route, point (N1, M1) is the end point of the route. Point coordinates are numbered starting from zero. The points can be the same. It is known that the total number of matrix elements is limited to 1,100,000.
After numbers height map is entered in rows - at first the first line, then the second, and so on. Height is a non-negative integer not exceeding 10000.

Print to standard output the total change in elevation while traversing the optimal route.

I came to conclusion that it's about shortest path in graph and wrote this
But for m=n=1000 program eats too much (~169MiB, mostly heap) memory.
Limits are as following:

Time limit: 2 s
Memory limit: 50M
Stack limit: 64M

I also wrote C++ program doing same thing with priority_queue(just to check, problem must be solved in C), but it still needs ~78MiB (mostly heap)

How should I solve this problem (use another algorithm, optimize existing C code or something else)?

Solution

You can fit a height value into a 16-bit unsigned int (uint_16_t, if using C++11). To store 1.1M of those 2-byte values requires 2.2M of memory. So far so good.

Your code builds an in-memory graph with linked lists and lots of pointers. Your heap-based queue also has a lot of pointers. You can greatly decrease memory usage by relying on a more-efficient representation - for example, you could build an NxM array of elements with

  struct Cell {
      uint_32_t distance; // shortest distance from start, initially INF
      uint_16_t height;
      int_16_t parent;    // add this to cell index to find parent; 0 for `none`
  };

A cell at row, col will be at index row + N*col in this array. I strongly recommend building utility methods to find each neighbor, which would return -1 to indicate "out of bounds" and a direct index otherwise. The difference between two indices would be usable in parent.

You can implement a (not very efficient) priority queue in C by calling stdlib's "sort" on an array of node indices, and sorting them by distance. This would cut a lot of additional overhead, as each pointer in your program probably takes 8 bytes (64-bit pointers).

By avoiding a lot of pointers, and using an in-memory description instead of a graph, you should be able to cut down memory consumption to

1.1M Cells x 8 bytes/cell                    = 8.8M
1.1M indices in the pq-array x 4 bytes/index = 4.4M

For a total of around 16 Mb w/overheads - well under stated limits. If it takes too long, you should use a better queue.