Program to find minimum matrix

It's a variant of the Traveling Salesman problem[^] (you have to visit all cells of the matrix) with an unusual cost function. The cost function can only be evaluated once you have a full path. Moreover a full path needs to visit all cells. You migth want to look up implementations of the Visitor Pattern[^] to get an idea on how the code might look like.

To solve the problem you need to enumerate all paths through the Matrix. Since you have no more than 4 directions to go from each cell, and the length of the path must be NxM, the total number of paths starting at cell (1,1) is less than 4^(N*M-1) (4 to the power of (N*M-1), but that's still a lot. It's probably best to avoid those paths that can't be a solution, e. g. by keeping track of which cells you already visited, and not choosing a direction towards a cell that you already visited.

The implementation can be simplified by treating the Matrix as a graph with it's cells as nodes. Each node has links to it's (up to) four neighbors, and maybe it could store index values of it's position in the matrix. For your algorithm, you should also add a link to the next cell in the path you're about to construct in case you visited it:

struct node {
    // links to neighbouring cells of the matrix (may be nullptr):
    node* up;
    node* down;
    node* left;
    node* right;
    // position of the cell within the matrix
    int row;
    int column;
    // next node of the current path
    node* next;
};
struct matrix {
    node* first;
};

To find a path, the most simple solution I can think of is making recursive calls with each cell you add to the path. For each step, you can choose to go in any of the four directions, provided that the pointer is not null (indicating you're at the boundary of the Matrix), and the next pointer of the cell you're going to is a nullptr (otherwise you've already visited it). The recursion is finished when there is no valid direction to go. The path is valid when it has reached a length of NxM.

All in all, that's a lot code to write, but if you follow the outline above it shouldn't be too hard.